Codeforces #652 Div2 E. DeadLee

まだ6月分か…。
http://codeforces.com/contest/1369/problem/E

問題

N種類の食事があり、それぞれの個数が与えられる。
ここにM人の人が来る。
各人は2つの好みの食事があり、来た順に2つの食事を1つずつ食べる。
この時、好みの食事がどちらも存在しない状態を避けたい。
条件を満たす、人が来る順番が存在するならそれを答えよ。

解法

もし、在庫の数がその食事を欲しい人数以上なら、その人たちはいつ来てもよいことになる。
そこで、その人たちは最後に来ることにしよう。
そうすると、その人たちのもう一つの好みの食事を必須とする人が減るので、キューを使い同じ手順で後ろから順番を決めていくことができる。

int N,M;
int W[202020];
int X[202020],Y[202020];
set<int> C[202020];
int ret[202020];
int did[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>W[i];
	}
	FOR(i,M) {
		cin>>X[i]>>Y[i];
		X[i]--;
		Y[i]--;
		C[X[i]].insert(i);
		C[Y[i]].insert(i);
	}
	
	vector<int> R;
	queue<int> Q;
	FOR(i,N) if(C[i].size()<=W[i]) did[i]=1,Q.push(i);
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		while(C[x].size()) {
			y=*C[x].begin();
			R.push_back(y+1);
			C[X[y]].erase(y);
			C[Y[y]].erase(y);
			if(did[X[y]]==0 && C[X[y]].size()<=W[X[y]]) did[X[y]]=1,Q.push(X[y]);
			if(did[Y[y]]==0 && C[Y[y]].size()<=W[Y[y]]) did[Y[y]]=1,Q.push(Y[y]);
			
		}
	}
	if(R.size()<M) return _P("DEAD\n");
	
	cout<<"ALIVE"<<endl;
	reverse(ALL(R));
	FORR(r,R) cout<<r<<" ";
	cout<<endl;
	
}

まとめ

解法を聞いちゃえば簡単だけど、普通に本番結構手間取ってるな。