結果

問題 No.3756 Udon Network
ユーザー tsunamayo123
提出日時 2026-09-11 22:09:09
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,556 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 161 ms
コンパイル使用メモリ 81,944 KB
実行使用メモリ 145,340 KB
最終ジャッジ日時 2026-10-09 17:42:23
合計ジャッジ時間 32,292 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
Example 0 % AC * 1 WA * 7
Subtask $1$ 2 % AC * 2 WA * 13
Subtask $2$ 4 % AC * 2 WA * 20
Subtask $3$ 8 % AC * 2 WA * 7
Subtask $4$ 16 % AC * 10
Subtask $5$ 32 % AC * 2 WA * 8
Subtask $6$ 38 % AC * 10 WA * 43
合計 4 * 16% = 64 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# 部分点4

import sys
from atcoder.dsu import DSU

input = sys.stdin.readline

N,M,Q = map(int, input().split())

A = list(map(int, input().split()))
A = [x-1 for x in A]

U = [0]*M
V = [0]*M
W = [0]*M

B = []

for j in range(M):
    U[j],V[j],W[j] = map(int, input().split())
    U[j]-=1
    V[j]-=1

    B.append((W[j],j))

B=sorted(B)

ans = [10**9+1] * N
uf = DSU(N)

color = A[:]

pending = [[] for _ in range(N)]
for i in range(N):
    pending[i].append(i)

def check(u,w):
    root = uf.leader(u)

    for v in pending[root]:
        ans[v]=w
    
    pending[root].clear()

for j in range(M):
    s,k = B[j]

    if not uf.same(U[k],V[k]):
        a = uf.leader(U[k])
        b = uf.leader(V[k])

        if (color[a]!=-1) and (color[b]==-1):
            color[a]=-1
            check(a,s)

        elif (color[a]==-1) and (color[b]!=-1):
            color[b]=-1
            check(b,s)

        elif (color[a]!=-1) and (color[b]!=-1):
            if color[a] != color[b]:
                color[a]=-1
                color[b]=-1
                check(a,s)
                check(b,s)

        n = uf.merge(a,b)

        if n!=a:
            for p in pending[a]:
                pending[n].append(p)
            pending[a].clear()

        if n!=b:
            for p in pending[b]:
                pending[n].append(p)
            pending[b].clear()

for k in range(Q):
    s,c = map(int,input().split())

    if c==1:
        print(0)
    
    if c==2:
        if ans[s-1]==10**9+1:
            print(-1)
        else:
            print(ans[s-1])
0