結果
問題 | No.74 貯金箱の退屈 |
ユーザー |
|
提出日時 | 2017-06-21 17:18:46 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,463 bytes |
コンパイル時間 | 1,021 ms |
コンパイル使用メモリ | 120,784 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 20:25:56 |
合計ジャッジ時間 | 1,804 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import std.stdio, std.array, std.string, std.conv, std.algorithm;import std.typecons, std.range, std.random, std.math, std.container;import std.numeric, std.bigint, core.bitop;void main() {auto N = readln.chomp.to!int;auto D = readln.split.map!(to!int).array;auto W = readln.split.map!(to!int).array;auto uf = new UnionFind(N);auto one = new bool[](N);foreach (i; 0..N) {auto a = (i + D[i]) % N;auto b = (i - D[i]) % N;b = (b + N) % N;uf.unite(a, b);if (a == b) one[a] = true;}bool ans = true;foreach (i; 0..N) {if (uf.table[i] >= 0) continue;bool ok = false;foreach (x; uf.group[i]) if (one[x]) ok = true;if (uf.group[i].map!(x => W[x] == 0).sum % 2 == 0) ok = true;ans &= ok;}writeln(ans ? "Yes" : "No");}class UnionFind {int N;int[] table;int[][] group;this(int n) {N = n;table = new int[](N);fill(table, -1);group = new int[][](N);foreach (i; 0..N) group[i] ~= i;}int find(int x) {return table[x] < 0 ? x : (table[x] = find(table[x]));}void unite(int x, int y) {x = find(x);y = find(y);if (x == y) return;if (table[x] > table[y]) swap(x, y);foreach (g; group[y]) group[x] ~= g;group[y] = [];table[x] += table[y];table[y] = x;}}