結果
問題 |
No.3093 Safe Infection
|
ユーザー |
![]() |
提出日時 | 2025-09-28 22:11:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 283 ms / 2,000 ms |
コード長 | 1,688 bytes |
コンパイル時間 | 4,311 ms |
コンパイル使用メモリ | 82,436 KB |
実行使用メモリ | 100,016 KB |
最終ジャッジ日時 | 2025-09-28 22:12:11 |
合計ジャッジ時間 | 17,740 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 71 |
ソースコード
def op(x, y): return max(x, y) class UnionFind: def __init__(self, n, A, op): self.n = n self.parent_size = [-1]*n self.A = A[:] self.op = op def leader(self, a): if self.parent_size[a] < 0: return a self.parent_size[a] = self.leader(self.parent_size[a]) return self.parent_size[a] def merge(self, a, b): x, y = self.leader(a), self.leader(b) if x == y: return l, r = self.A[x], self.A[y] if abs(self.parent_size[x]) < abs(self.parent_size[y]): x, y = y, x self.parent_size[x] += self.parent_size[y] self.parent_size[y] = x self.A[x] = self.op(l, r) return def __getitem__(self, n): return self.A[self.leader(n)] def update(self, n, a): self.A[self.leader(n)] = a def same(self, a, b): return self.leader(a) == self.leader(b) def size(self, a): return abs(self.parent_size[self.leader(a)]) def groups(self): result = [[] for _ in range(self.n)] for i in range(self.n): result[self.leader(i)].append(i) return [r for r in result if r != []] N, M, K = map(int, input().split()) A = list(map(int, input().split())) G = [[] for _ in range(N)] for _ in range(M): u, v = map(int, input().split()) u, v = u-1, v-1 G[u].append(v) G[v].append(u) B = sorted([(a, i) for i, a in enumerate(A)], key=lambda x:x[0]) UF = UnionFind(N, A, op) for b, idx in B: for v in G[idx]: if UF[v] <= UF[idx] and UF[idx]-UF[v] <= K: UF.merge(idx, v) print("Yes" if UF.size(0) == N else "No")