Codeforces #455 Div2 E. Coprocessor

問題文の解釈に手間取った。
http://codeforces.com/contest/909/problem/E

問題

複数のタスクがあり、それらを処理していく。
タスク同士には依存関係がある場合があり、その場合先に依存先のタスクを終えなければならない。
なお、タスクの依存関係はDAGを成す。

ここで、タスクにはCPUで処理するものとコプロセッサで処理するものがある。
コプロセッサは、コプロセッサを用いて処理する複数のタスクに関し１度に処理を行うことができる。
ただし、同時に処理できるのは、互いに直接依存関係にあるか、もしくはまったく依存関係がなく、依存先がすべて処理完了済みの場合に限る。

全タスク完了には最小でコプロセッサを何回用いる必要があるか。

解法

依存関係が0-1-1-0-0-1-0-1のようにチェインを成すとすると、1の連結成分同士は同時に処理できないので、その数が必要処理回数となる。
よってすべてのチェインに関し、1の連結成分数の最大値を数えよう。
これはトポロジカルソート順で各タスク実行時の処理回数を数えていくDPで良い。

int N,M;
int C[101010];
vector<int> E[101010];
int in[101010];
int did[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	FOR(i,N) scanf("%d",&C[i]);
	FOR(i,M) {
		scanf("%d%d",&x,&y);
		E[y].push_back(x);
		in[x]++;
	}
	
	queue<int> Q;
	FOR(i,N) if(in[i]==0) Q.push(i);
	int ret=0;
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		if(C[x]==1) did[x]=max(did[x],1);
		FORR(e,E[x]) {
			in[e]--;
			if(in[e]==0) Q.push(e);
			did[e]=max(did[e],did[x]+(C[x]==0&&C[e]==1));
			
		}
		ret=max(ret,did[x]);
	}
	cout<<ret<<endl;
	
}

まとめ

問題文の理解に手間取ってpretestを数回WAした。