Submission #67475472

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int a[10005],b[10005],l[10005],r[10005];
vector<int> V[4000005],reV[4000005];
int pos(int i,int j,int p){
	if(p==0) return (i-1)*(m+2)+j+1;
	else return pos(i,j,0)+pos(n,m+1,0);
}
void add(int u,int v){
//	cout<<u<<" "<<v<<"\n"; 
	V[u].push_back(v);
	reV[v].push_back(u);
}
int vis[4000005];
stack<int> S;
void dfs1(int u){
	vis[u]=1;
	for(int v:V[u]){
		if(vis[v]) continue;
		dfs1(v);
	}
	S.push(u);
}
int id[4000005];
void dfs2(int u,int t){
	id[u]=t;
	for(int v:reV[u]){
		if(id[v]) continue;
		dfs2(v,t);
	}
}
int main(){
	cin>>n>>m>>q;
	for(int i=1;i<=q;i++){
		cin>>a[i]>>b[i]>>l[i]>>r[i];
	}
	for(int i=1;i<=n;i++){
		add(pos(i,0,0),pos(i,0,1));
		add(pos(i,m+1,1),pos(i,m+1,0));
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m+1;j++){
			if(j!=0) add(pos(i,j,1),pos(i,j-1,1));
			if(j!=m+1) add(pos(i,j,0),pos(i,j+1,0));
		}
	}
	for(int i=1;i<=q;i++){
		int A=a[i],B=b[i],L=l[i],R=r[i];
		for(int j=0;j<=m+1;j++){
			if(R-j+1<=m+1){
				add(pos(A,j,1),pos(B,max(0,R-j+1),0));
				add(pos(B,j,1),pos(A,max(0,R-j+1),0));
			}
			if(L-j+1>=0){
				add(pos(A,j,0),pos(B,min(m+1,L-j+1),1));
				add(pos(B,j,0),pos(A,min(m+1,L-j+1),1));
			}
		}
	}
	for(int i=1;i<=pos(n,m+1,1);i++){
		if(!vis[i]) dfs1(i);
	}
	int cnt=0;
	while(!S.empty()){
		int u=S.top();
		S.pop();
		if(!id[u]) dfs2(u,++cnt);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m+1;j++){
			if(id[pos(i,j,1)]==id[pos(i,j,0)]){
				cout<<"-1\n";
				return 0;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(id[pos(i,j,1)]  > id[pos(i,j,0)]&&
			   id[pos(i,j+1,1)]<=id[pos(i,j+1,0)]){
				cout<<j<<" ";
				break;
			}
		}
	}
	return 0; 
}

Submission Info

Judge Result