結果

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

ソースコード

diff # 

import heapq
# 根を求める
cnt = 0
def root(x):
    if par[x] == -1: return x # x が根の場合は x を返す
    else:
        par[x] = root(par[x]) # 経路圧縮
        A[par[x]-1] = max(A[x-1],A[par[x]-1])
        A[x-1] = max(A[par[x]-1],A[x-1])
        return par[x]
# x を含むグループと y を含むグループを併合する
def unite(x, y):
    global check
    global cnt
    # x 側と y 側の根を取得する
    rx = root(x)
    ry = root(y)
    if rx == ry: return False # すでに同じグループのときは何もしない
    # union by rank
    cnt += 1
    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

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]]:
        if cnt +1 == N:
            break
        unite(b,l[1])
print("Yes" if check else "No")
#print(A,par)
0