結果
問題 | No.3093 Safe Infection |
ユーザー |
![]() |
提出日時 | 2025-04-06 20:35:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 404 ms / 2,000 ms |
コード長 | 1,584 bytes |
コンパイル時間 | 526 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 107,540 KB |
最終ジャッジ日時 | 2025-04-06 20:36:08 |
合計ジャッジ時間 | 18,122 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 70 |
ソースコード
class UnionFind: def __init__(self, n: int): self.data = [-1] * (n+1) self.nexts = [i for i in range(n+1)] def root(self, a: int) -> int: if self.data[a] < 0: return a self.data[a] = self.root(self.data[a]) return self.data[a] def unite(self, a: int, b: int) -> bool: pa = self.root(a) pb = self.root(b) if pa == pb: return False if self.data[pa] > self.data[pb]: pa, pb = pb, pa self.data[pa] += self.data[pb] # pa を pb をつなげる self.data[pb] = pa self.nexts[pa], self.nexts[pb] = self.nexts[pb], self.nexts[pa] return True def is_same(self, a: int, b: int) -> bool: return self.root(a) == self.root(b) def size(self, a: int) -> int: """a が属する集合のサイズ""" return -self.data[self.root(a)] def group(self, a: int): """a が属する集合""" yield a x = a while self.nexts[x] != a: x = self.nexts[x] yield x N, M, K = map(int, input().split()) A = list(map(int, input().split())) edges = [] for _ in range(M): u, v = map(lambda x: int(x)-1, input().split()) ma = max(A[u], A[v]) edges.append((ma, u, v)) t = A.copy() uf = UnionFind(N) for _, u, v in sorted(edges): ru = uf.root(u) rv = uf.root(v) d = abs(t[ru] - t[rv]) if d <= K: uf.unite(ru, rv) r = uf.root(ru) t[r] = max(t[ru], t[rv]) if len(set(uf.root(i) for i in range(N))) == 1: print('Yes') else: print('No')