kmjp's blog

競技プログラミング参加記です

Codeforces #669 Div2 E. Egor in the Republic of Dagestan

当日途中で抜けちゃったけど、割と簡単目な回だった様子。
https://codeforces.com/contest/1407/problem/E

問題

DAGを成す有向グラフが与えられる。
各辺、白か黒で塗られている。

このグラフにおいて、各点を白黒で塗り分けたい。
この際、各点からは、その点と同色の辺に沿って隣接する点に移動できるとする。
頂点1からNに到達できないような彩色例があればそれを示せ。
それが存在しない場合、最短路が最長となるような彩色例を示せ。

解法

頂点Nに近いところから、辺の逆向きに頂点Nまでの最短路長を確定させていく。

いま頂点v→Nの最短路長が確定したとする。
頂点u→vに辺がある場合、uの色が未確定なら、その辺とは逆の色に塗ろう。
uの色が確定済みで、u→vの辺の色と一致する場合、しょうがないので頂点u→Nの最短路長を頂点v→Nの最短路長+1とする。
上記手順をBFSの要領で行っていこう。

int N,M;
vector<pair<int,int>> E[505050];

int D[505050];
int C[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	FOR(i,M) {
		scanf("%d%d%d",&x,&y,&j);
		E[y-1].push_back({x-1,j});
	}
	FOR(i,N) {
		D[i]=-1;
		C[i]=2;
	}
	
	D[N-1]=0;
	queue<int> Q;
	Q.push(N-1);
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		FORR2(e,c,E[x]){
			if(C[e]!=c) {
				C[e]=1-c;
			}
			else if(D[e]==-1) {
				D[e]=D[x]+1;
				Q.push(e);
			}
				
		}
	}
	cout<<D[0]<<endl;
	FOR(i,N) {
		if(C[i]==2) C[i]=0;
		cout<<C[i];
	}
	cout<<endl;
	
}

まとめ

Div2とはいえ最終問題の割に簡単?