結果

問題 No.3309 Aging Railway
コンテスト
ユーザー moon17
提出日時 2025-10-26 12:12:04
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 534 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 230 ms
コンパイル使用メモリ 95,976 KB
実行使用メモリ 297,712 KB
最終ジャッジ日時 2026-07-16 00:38:51
合計ジャッジ時間 5,785 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import*
(n,m),*e=[[*map(int,s.split())]for s in open(0)]
uv,st=e[:-m],e[-m:]
c=defaultdict(int)
ns=set()
for s,t in st:
  s-=1;t-=1
  c[s,t]+=1
  ns.add((s,t))
ans=[0]
uf=[*range(n)]
def find(x):
 q=[]
 while uf[x]^x:q+=x,;x=uf[x]
 for p in q:uf[p]=x
 return x
def unite(x,y):
 x,y=find(x),find(y)
 if x^y:uf[x]=y
for i in range(n-1)[::-1]:
  u,v=e[i]
  unite(u-1,v-1)
  ans+=ans[-1],
  q=set()
  for s,t in ns:
    if find(s)==find(t):
      q.add((s,t))
      ans[-1]+=c[s,t]
  ns-=q
print(*ans[:-1][::-1],sep='\n')
0