kmjp's blog

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

Codeforces #266 Div2 E. Information Graph

これは結構手間取ったけど、最終的に1発正答できてよかった。
http://codeforces.com/contest/466/problem/E

問題

N人の人がいる。以下の順にM個のクエリを処理せよ。

  1. Y番の人がX番の人の直接のボスになる。各人はボスを2人以上持つことはない。
  2. Z番の人に書類を回すと、順々にサインをしながら直接のボスに渡していく。ボスがいない人に到達したらその書類は保存される。
  3. 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++;
		}
	}
}

まとめ

まぁ解けて良かった。
だいぶダブリングに慣れてきた気がする。