結果

問題 No.3200 Sinking Islands
ユーザー miho-4
提出日時 2025-07-11 22:02:05
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 547 bytes
コンパイル時間 733 ms
コンパイル使用メモリ 81,572 KB
実行使用メモリ 67,452 KB
最終ジャッジ日時 2025-07-11 22:02:09
合計ジャッジ時間 3,960 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

from atcoder.dsu import DSU

n,m=map(int,input().split())
edge=[list(map(int,input().split())) for _ in range(m)]
q=int(input())
Q=[int(input())-1 for _ in range(q)]
QS=set(Q)

G=DSU(n)
for i in range(m):
  if i not in QS:
    a,b=edge[i]
    a-=1
    b-=1
    G.merge(a,b)

UF=G.groups()

tmp=0
for e in UF:
  tmp+=(n-len(e))*len(e)
cnt=tmp//2

ans=[]
for i in Q[::-1]:
  ans.append(cnt)
  a,b=edge[i]
  a-=1
  b-=1
  if G.same(a,b):
    pass
  else:
    A=G.size(a)
    B=G.size(b)
    cnt-=A*B
    G.merge(a,b)
  
for e in ans[::-1]:
  print(e)
0