結果
| 問題 |
No.3093 Safe Infection
|
| コンテスト | |
| ユーザー |
detteiuu
|
| 提出日時 | 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")
detteiuu