結果

問題 No.3200 Sinking Islands
ユーザー むつある
提出日時 2025-07-11 21:58:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 648 ms / 2,000 ms
コード長 844 bytes
コンパイル時間 347 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 135,808 KB
最終ジャッジ日時 2025-07-11 21:58:40
合計ジャッジ時間 13,060 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

def find(x):
  if tree[x]<0:
    return x
  tree[x] = find(tree[x])
  return tree[x]
    
def unite(x,y):
  x=find(x)
  y=find(y)
  if x == y:
    return
  else:
    if tree[x] > tree[y]:
      x,y=y,x
    tree[x]+=tree[y]
    tree[y]=x
    
n,m=map(int,input().split())    
tree=[-1]*n

c=[0]*m
g=[]
for _ in range(m):
  u,v=map(int,input().split())
  u-=1
  v-=1
  g.append([u,v])
  
q=int(input())
v=[]
for _ in range(q):
  b=int(input())
  b-=1
  v.append(b)
  c[b]=1

  
for i in range(m):
  if c[i]:
    continue
  unite(g[i][0],g[i][1])
  
now=[]
for i in tree:
  if i<0:
    now.append(-i)
    

    
ans=0
for i in now:
  ans+=i*(n-i)
ans//=2

fans=[]

while v:
  fans.append(ans)
  b=v.pop()
  p,q=g[b]
  if find(p)==find(q):
    continue
  x,y=tree[find(p)],tree[find(q)]
  ans-=x*y
  unite(p,q)
  
while fans:
  print(fans.pop())
0