結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
|
提出日時 | 2025-07-11 22:05:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 603 ms / 2,000 ms |
コード長 | 635 bytes |
コンパイル時間 | 618 ms |
コンパイル使用メモリ | 82,604 KB |
実行使用メモリ | 224,488 KB |
最終ジャッジ日時 | 2025-07-11 22:05:38 |
合計ジャッジ時間 | 12,845 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
(n,m),*e=[[*map(int,s.split())]for s in open(0)] uv=[(u-1,v-1)for u,v in e[:m]] q=e[m][0] bs=[i[0]-1 for i in e[m+1:]] uf=[*range(n)] d=[1]*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:return if d[x]>d[y]:x,y=y,x uf[x]=y;d[y]+=d[x] f={*range(m)}-{*bs} for i in f: unite(*uv[i]) l=[[]for _ in range(n)] for i in range(n): l[find(i)]+=i, now=1 for i in range(n): t=len(l[i]) now+=t*(n-t) now//=2 ans=[now] for i in bs[::-1]: u,v=uv[i] u,v=find(u),find(v) if u!=v: now-=d[u]*d[v] unite(u,v) ans+=now, print(*ans[::-1][1:],sep='\n')