結果

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

ソースコード

diff #
raw source code 

# 部分点5

from atcoder.dsu import DSU

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)

S = [0]*Q
C = [0]*Q

for k in range(Q):
    S[k],C[k] = map(int,input().split())
    S[k]-=1

ok = [M]*Q
ng = [-1]*Q

while True:
    mid = [[] for _ in range(M)]
    fin = True

    for k in range(Q):
        if C[k]==1:
            continue
        
        if (ok[k]-ng[k])>1:
            fin=False
            m=(ok[k]+ng[k])//2
            mid[m].append(k)

    if fin:
        break

    uf = DSU(N)

    for j in range(M):
        t = B[j][1]
        uf.merge(U[t],V[t])

        for k in mid[j]:
            if uf.size(S[k]) >= C[k]:
                ok[k]=j
            else:
                ng[k]=j
    
for k in range(Q):
    # -1は制約上起こり得ない
    if C[k]==1:
        print(0)
    else:
        print(B[ok[k]][0])
0