CF285に参加。
ABをさっさと解いたところ、CDは解けなかったけど大量にCDが落ちたため結構良い順位に落ち着いた。
http://codeforces.com/contest/504/problem/A
問題
0~(N-1)の番号を持つN個の頂点からなる、森を成すグラフがある。
ここで、各頂点に対し、辺で直接接続された頂点の数と、それら頂点の番号のxorを取った値S[i]が与えられる。
グラフを構成する辺を列挙せよ。
解法
グラフが森を成すということは閉路がない。
そのため、辺があるならば次数1の頂点が必ず存在するはずである。
また、次数1の頂点iに対しては、S[i]は接続された頂点番号を示すはずである。
よって、iとS[i]をつなぐ辺が存在する。
そのような辺を解に追加すると同時に、S[i]番の頂点の次数を1つ減らし、S[S[i]] ^= iでS[S[i]]を更新する。
1個辺を追加するごとにどこかの頂点の次数が1個減るので、連鎖的に次数1の頂点が発生するため順次処理していけば良い。
int N; int D[1<<17],S[1<<17]; vector<pair<int,int> > V; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; queue<int> Q; FOR(i,N) { cin>>D[i]>>S[i]; if(D[i]==1) Q.push(i); } while(Q.size()) { int k=Q.front(); Q.pop(); if(D[k]==0) continue; D[k]--; x=S[k]; V.push_back(make_pair(k,x)); D[x]--; S[x]^=k; if(D[x]==1) Q.push(x); } _P("%d\n",V.size()); FOR(i,V.size()) _P("%d %d\n",V[i].first,V[i].second); }
まとめ
次数1の点のS[i]は接続先を示す、ということに気づけばすぐだね。
Div1Aとしてお手頃な良問だと思う。