Codeforces #417 Div2 D. Sagheer and Kindergarten

赤い人もほとんど解けていないのは問題の内容よりは問題文のせいだと思いたい。
http://codeforces.com/contest/812/problem/D

問題

N人の赤ん坊とM個のおもちゃがある。
各赤ん坊はいくつかのおもちゃを手に取り遊びたい。

• 各赤ん坊は自身が欲しいおもちゃをすべて手に入れると満足してすべてを解放する。
• 赤ん坊は異なるタイミングでおもちゃを欲しがる。
  • そのおもちゃが誰にもキープされていない場合、それをキープする。
  • 欲しいおもちゃを他の赤ん坊がキープしている場合、その赤ん坊がおもちゃを解放するまで待つ。
  • 複数の赤ん坊が同じおもちゃを待っている場合、おもちゃが解放されると待っていた順でそれをキープする。

すでに赤ん坊が何かのおもちゃを待っている場合、他のおもちゃが欲しくなっても手を出さない。

赤ん坊がおもちゃを欲しがるタイミングと対象が1つを除き与えられている。
この状態でおもちゃ待ちのデッドロックがないことがわかっている。

末尾のおもちゃ要求のクエリがQ個与えられる。
各クエリについて、その要求によりデッドロックが生じる赤ん坊の数を答えよ。

解法

赤ん坊xがおもちゃを欲しがるとき、先にそのおもちゃを欲しがった人yがいたとき、y→xに辺を張ったグラフを考えよう。
この辺はyがおもちゃを解放したしないにかかわらず張る(末尾の要求による新たに解放しないケースが生じる可能性があるため)。
ただし、すでにxに辺が張られている場合は張らない(他のおもちゃを待っている状態)

最後のおもちゃ要求は赤ん坊aがおもちゃzを欲しがったとする。
おもちゃzが解放済みならデッドロックは生じない。
直前にzを使った人をbとしよう。
この要求はグラフにb→aの辺を加えることに相当する。

元のグラフは森を成すが、この処理により閉路が生じた場合、bのsubtree内の頂点でデッドロックが生じる。
事前にEuler Tourを実行しておき、デッドロックした頂点のSubTreeの頂点数を答えていこう。

int N,M,K,Q;
int A[101010],B[101010];
vector<int> E[101010];
int pre[101010];
int waiting[101010];
int in[101010];

int id,L[101010],R[101010];

void dfs(int cur) {
	L[cur]=id++;
	FORR(e,E[cur]) dfs(e);
	R[cur]=id;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(pre);
	cin>>N>>M>>K>>Q;
	FOR(i,K) {
		cin>>A[i]>>B[i];
		A[i]--;
		if(waiting[A[i]]==0 && pre[B[i]]>=0) {
			E[pre[B[i]]].push_back(A[i]);
			in[A[i]]++;
			waiting[A[i]]++;
		}
		pre[B[i]]=A[i];
	}
	FOR(i,N) if(in[i]==0) dfs(i);
	
	while(Q--) {
		cin>>x>>y;
		x--;
		y = pre[y];
		if(y>=0 && L[x]<=L[y] && L[y]<R[x]) cout<<R[x]-L[x]<<endl;
		else cout<<0<<endl;
	}
	
}

まとめ

実装は軽いのだが、とにかく題意の理解が大変。