結果

問題 No.3309 Aging Railway
コンテスト
ユーザー titia
提出日時 2025-10-26 13:32:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,394 ms / 3,000 ms
コード長 1,586 bytes
コンパイル時間 365 ms
コンパイル使用メモリ 82,276 KB
実行使用メモリ 223,512 KB
最終ジャッジ日時 2025-10-26 13:32:49
合計ジャッジ時間 31,142 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://betrue12.hateblo.jp/entry/2019/08/14/152227
# のコードを改造

import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N,M=map(int,input().split())
U=[tuple(map(int,input().split())) for i in range(N-1)]
U.reverse()
Queries=[tuple(map(int,input().split())) for i in range(M)]

# UnionFind

Group = [i for i in range(N+5)] # グループ分け
Nodes = [1]*(N+5) # 各グループのノードの数

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):
    if find(x) != find(y):
        if Nodes[find(x)] < Nodes[find(y)]:
            
            Nodes[find(y)] += Nodes[find(x)]
            Nodes[find(x)] = 0
            Group[find(x)] = find(y)
            
        else:
            Nodes[find(x)] += Nodes[find(y)]
            Nodes[find(y)] = 0
            Group[find(y)] = find(x)

OK=[N-1]*M
NG=[-1]*M


for tests in range(13):
    Group = [i for i in range(N+5)] # グループ分け
    Nodes = [1]*(N+5) # 各グループのノードの数
    K=[[] for i in range(N+5)]

    for i in range(M):
        if OK[i]==-1:
            continue
        K[(OK[i]+NG[i])//2].append(i)

    for i in range(N-1):
        x,y=U[i]
        Union(x,y)

        for ind in K[i]:
            s,t=Queries[ind]

            if find(s)==find(t):
                OK[ind]=i
            else:
                NG[ind]=i

OK.sort(reverse=True)

ANS=[]
now=M
ind=0

for i in range(N-2,-1,-1):
    while ind<len(OK) and OK[ind]==i:
        now-=1
        ind+=1

    ANS.append(now)

print("\n".join(map(str,ANS)))
0