結果

問題 No.74 貯金箱の退屈
ユーザー antaanta
提出日時 2014-11-21 00:42:51
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,460 bytes
コンパイル時間 514 ms
コンパイル使用メモリ 64,784 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-30 22:02:07
合計ジャッジ時間 1,787 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 1 ms
4,384 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 1 ms
4,380 KB
testcase_26 AC 2 ms
4,376 KB
testcase_27 AC 1 ms
4,376 KB
testcase_28 AC 2 ms
4,380 KB
testcase_29 AC 1 ms
4,380 KB
testcase_30 AC 1 ms
4,380 KB
testcase_31 AC 2 ms
4,380 KB
testcase_32 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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