結果

問題 No.3093 Safe Infection
コンテスト
ユーザー Ruseu29
提出日時 2025-04-06 17:40:04
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,642 bytes
コンパイル時間 583 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 44,788 KB
最終ジャッジ日時 2025-04-06 17:40:38
合計ジャッジ時間 29,683 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 WA * 56
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq


# 根を求める
def root(x):
    if par[x] == -1: return x # x が根の場合は x を返す
    else:
        par[x] = root(par[x]) # 経路圧縮
        return par[x]
# x と y が同じグループに属するか (根が一致するか)
def issame(x, y):
    return root(x) == root(y)
# x を含むグループと y を含むグループを併合する
def unite(x, y):
    global check
    # x 側と y 側の根を取得する
    rx = root(x)
    ry = root(y)

    if rx == ry: return False # すでに同じグループのときは何もしない
    # union by rank
    if rank[rx] < rank[ry]: # ry 側の rank が小さくなるようにする
        rx, ry = ry, rx
    if abs(A[ry-1] - A[rx-1]) > K:
        check = False
    A[rx-1] = max(A[ry-1],A[rx-1])
    par[ry] = rx # ry を rx の子とする
    if rank[rx] == rank[ry]: # rx 側の rank を調整する
        rank[rx] += 1
    siz[rx] += siz[ry] # rx 側の siz を調整する
    return True
# x を含む根付き木のサイズを求める
def size(x):
    return siz[root(x)]
    
N,Q,K = map(int,input().split())

par = [-1] * (N+1)
rank = [0] * (N+1)
siz = [1] * (N+1)
A = list(map(int,input().split()))
end = max(A)
bridge = [[] for n in range(N+1)]
check = True
tmp = []
for a in range(len(A)):
    tmp.append([A[a],a+1])
tmp.sort()
heapq.heapify(tmp)
for q in range(Q):
    a,b = map(int,input().split())
    bridge[a].append(b)
    bridge[b].append(a)
from collections import deque
ans = deque()
for n in range(N):
    l = heapq.heappop(tmp)
    for b in bridge[l[1]]:
        unite(b,l[1])
print("Yes" if check else "No")
# print(A,par)
0