結果

問題 No.74 貯金箱の退屈
コンテスト
ユーザー anta
提出日時 2014-11-21 00:42:51
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,460 bytes
コンパイル時間 830 ms
コンパイル使用メモリ 69,092 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-01-02 19:45:15
合計ジャッジ時間 1,927 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> D(N), W(N);
	for(int i = 0; i < N; ++ i) cin >> D[i];
	for(int i = 0; i < N; ++ i) cin >> W[i];
	vector<vector<int> > g(N);
	vector<bool> loop(N, false);
	for(int i = 0; i < N; ++ i) {
		int l = ((i - D[i]) % N + N) % N, r = (i + D[i]) % N;
		if(l != r) {
			g[l].push_back(r);
			g[r].push_back(l);
		}else {
			loop[i] = true;
		}
	}
	//グラフの連結成分に対して全域木を考える。
	//ある頂点対を結ぶその木上の唯一のパスに対してflipしていけば、任意の2つの頂点をflipできる。
	//よって、連結成分中にflipしたいものが偶数個あるならそれらを全てflipすることが可能。必要性は自明。
	//ただし、self-loopを含むならそれを偶奇に応じて任意にflipできるので常に可能。
	vector<bool> vis(N, false);
	vector<int> q(N);
	bool ans = true;
	for(int i = 0; i < N; ++ i) if(!vis[i]) {
		int t = 0;
		vis[i] = true;
		q[t ++] = i;
		for(int h = 0; h < t; ) {
			int u = q[h ++];
			for(int v : g[u]) {
				if(!vis[v]) {
					vis[v] = true;
					q[t ++] = v;
				}
			}
		}
		bool hasLoop = false;
		int flips = 0;
		for(int i = 0; i < t; ++ i) {
			int u = q[i];
			hasLoop |= loop[u];
			flips += W[u] == 0;
		}
		ans &= hasLoop || flips % 2 == 0;
	}
	puts(ans ? "Yes" : "No");
	return 0;
}
0