結果
問題 | No.74 貯金箱の退屈 |
ユーザー |
![]() |
提出日時 | 2020-12-14 22:12:13 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 32 ms / 5,000 ms |
コード長 | 1,418 bytes |
コンパイル時間 | 127 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-09-20 00:56:00 |
合計ジャッジ時間 | 2,196 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
class UF_tree:def __init__(self, n):self.root = [-1] * (n + 1)self.rank = [0] * (n + 1)def find(self, x):if self.root[x] < 0:return xelse:self.root[x] = self.find(self.root[x])return self.root[x]def isSame(self, x, y):return self.find(x) == self.find(y)def unite(self, x, y):x = self.find(x)y = self.find(y)if x == y:returnelif self.rank[x] < self.rank[y]:self.root[y] += self.root[x]self.root[x] = yelse:self.root[x] += self.root[y]self.root[y] = xif self.rank[x] == self.rank[y]:self.rank[x] += 1def size(self, x):return -self.root[self.find(x)]N = int(input())D = list(map(int, input().split()))W = list(map(int, input().split()))slf = [0] * Nuf = UF_tree(N)for i, d in enumerate(D):x = (i + d) % Ny = (i - d % N + N) % Nif x == y:slf[x] = 1else:uf.unite(x, y)leader = set(uf.find(i) for i in range(N))group = {i: [] for i in leader}for i in range(N):group[uf.find(i)].append(i)ok = Truefor g in group.values():cnt = sum(1 - W[i] for i in g)if cnt % 2 == 0:continueif sum(slf[i] for i in g):continueok = Falseif ok:print("Yes")else:print("No")