結果
問題 | 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 x else: 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: return elif self.rank[x] < self.rank[y]: self.root[y] += self.root[x] self.root[x] = y else: self.root[x] += self.root[y] self.root[y] = x if self.rank[x] == self.rank[y]: self.rank[x] += 1 def 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] * N uf = UF_tree(N) for i, d in enumerate(D): x = (i + d) % N y = (i - d % N + N) % N if x == y: slf[x] = 1 else: 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 = True for g in group.values(): cnt = sum(1 - W[i] for i in g) if cnt % 2 == 0: continue if sum(slf[i] for i in g): continue ok = False if ok: print("Yes") else: print("No")