当日途中で抜けちゃったけど、割と簡単目な回だった様子。
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とはいえ最終問題の割に簡単?