これは結構手間取ったけど、最終的に1発正答できてよかった。
http://codeforces.com/contest/466/problem/E
問題
N人の人がいる。以下の順にM個のクエリを処理せよ。
- Y番の人がX番の人の直接のボスになる。各人はボスを2人以上持つことはない。
- Z番の人に書類を回すと、順々にサインをしながら直接のボスに渡していく。ボスがいない人に到達したらその書類は保存される。
- W番の人がI番目の書類にサインしたかどうか答える。
解法
書類とかサインとかいうと分かりにくいので、まずは問題文を読み替える。
ボスと部下の関係を親子関係で表すと、全体は根付き木からなる森になる。
3番目のクエリは、その書類を回した時点で、W番の人がZ番の人のボスかどうかを答えるものである。
ボスの部下の関係は追加することはあっても変更・削除されることはない。
よって、まず1番のクエリを全部実行してできる森を求めておく。
さらに各人の根からの深さや、親子関係をダブリングしておく。
また、3番目のクエリに対しては、クエリの時点で実行するのではなく、対応する書類を回す2番目のクエリの時点で実行するようにする。
ここでUnion-findを用いて、クエリ2周目では以下のように処理をしていく。
- 1番目のクエリに対してはUnion-findで木を連結する。
- 2番目のクエリに対しては、後で登場する対応する3番目のクエリを先に処理する。
- まずUnion-FindでZとWが連結しているか判定する。連結してないならサイン不可。
- WがZより浅い位置にあるか判定する。浅い位置にないならサイン不可。
- ダブリングした結果を用いて、ZからZとWの深さの差分だけ親をたどったとき、Wと一致するならサインをしている。
- 3番目のクエリに対しては、処理済みの結果を表示するだけ。
上記処理はダブリングやUnion-FindでO(M*logM)程度の計算量だが、どうも単純に親をたどる方式でO(M^2)でも間に合うようだ。
int N,M; vector<int> T; vector<int> QQ[100000]; vector<int> E[100001]; int D[100001]; int Q[100001][3]; int P[20][100001]; int res[100001]; class UF { public: static const int ufmax=100052; int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax]; UF() { init();} void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } } int find(int x) { return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));} int operator[](int x) {return find(x);} int count(int x) {return ufcnt[find(x)];} void unite(int x,int y) { x = find(x); y = find(y); if(x==y) return; if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x]; else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;} } }; void dfs(int cur,int d) { int i; D[cur]=d; FOR(i,E[cur].size()) dfs(E[cur][i],d+1); } void solve() { int i,j,k,l,r,x,y; string s; int pa=0; cin>>N>>M; FOR(i,N) P[0][i]=i; FOR(i,M) { cin>>j>>x; Q[i][0]=j; Q[i][1]=--x; if(j==1 || j==3) cin>>Q[i][2], Q[i][2]--; if(j==1) P[0][x]=Q[i][2], E[Q[i][2]].push_back(x); if(j==3) QQ[Q[i][2]].push_back(i); } FOR(x,19) FOR(i,N) P[x+1][i]=P[x][P[x][i]]; FOR(i,N) if(P[x][i]==i) dfs(i,0); UF uf; int hoge=0; FOR(i,M) { if(Q[i][0]==1) uf.unite(Q[i][1],Q[i][2]); if(Q[i][0]==3) _P(res[i]?"YES\n":"NO\n"); if(Q[i][0]==2) { FOR(j,QQ[hoge].size()) { int v=Q[QQ[hoge][j]][1]; if(uf[v]!=uf[Q[i][1]]) continue; if(D[v]>D[Q[i][1]]) continue; int cur=Q[i][1]; y=D[Q[i][1]]-D[v]; FOR(x,17) if(y&(1<<x)) cur=P[x][cur]; res[QQ[hoge][j]]=cur==v; } hoge++; } } }
まとめ
まぁ解けて良かった。
だいぶダブリングに慣れてきた気がする。