Codeforces #647 Div1 A. Johnny and Contribution

この時、翌日なんかがあったから不参加なんだったかな。
http://codeforces.com/contest/1361/problem/A

問題

N要素の無向グラフが与えられる。
各頂点には目標値が設定されている。

初期状態で各頂点は値が未設定である。
任意の順で頂点を訪問したとき、その頂点には、隣接する設定済みの値に対するmex値が設定される。

目標値を達成する訪問順を答えよ。

解法

mexの計算方法を考えると、値の小さい順に訪問する一択である。
あとは、その場合に目標値が隣接点の目標値に対するmexであるかを確認しよう。

int N,M;
int A[505050],B[505050];
vector<int> E[505050];
int T[505050];
vector<int> C[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	FOR(i,M) {
		scanf("%d%d",&A[i],&B[i]);
		E[A[i]-1].push_back({B[i]-1});
		E[B[i]-1].push_back({A[i]-1});
	}
	FOR(i,N) {
		scanf("%d",&T[i]);
		T[i]--;
		C[T[i]].push_back(i+1);
	}
	FOR(i,N) {
		set<int> S;
		FORR(e,E[i]) S.insert(T[e]);
		x=0;
		while(S.count(x)) x++;
		if(x!=T[i]) return _P("-1\n");
	}
	
	
	FOR(i,N) FORR(c,C[i]) cout<<c<<" ";
	cout<<endl;
	
}

まとめ

内容はともかく、問題文が長くて読むのつらいな。