結果

問題 No.3200 Sinking Islands
ユーザー alcea
提出日時 2025-07-11 21:49:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 470 ms / 2,000 ms
コード長 1,127 bytes
コンパイル時間 2,067 ms
コンパイル使用メモリ 202,588 KB
実行使用メモリ 9,472 KB
最終ジャッジ日時 2025-07-11 21:50:00
合計ジャッジ時間 11,153 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
struct unionfind{
  vector<int> par;
  unionfind(int n):par(n,-1){}
  int root(int x){return par[x]<0?x:par[x]=root(par[x]);}
  bool merge(int x,int y){
    x=root(x);y=root(y);
    if(x==y) return false;
    if(par[x]>par[y]) swap(x,y);
    par[x]+=par[y];par[y]=x;
    return true;
  }
  bool same(int x,int y){return root(x)==root(y);}
  int size(int x){return -par[root(x)];}
};
int main(){
  int n,m;
  cin>>n>>m;
  int u[m],v[m];
  for(int i=0;i<m;i++){
    cin>>u[i]>>v[i];
    u[i]--;v[i]--;
  }
  int q;
  cin>>q;
  int b[q];
  for(int i=0;i<q;i++) cin>>b[i],b[i]--;
  int check[m]{};
  for(int i=0;i<q;i++) check[b[i]]=1;
  unionfind U(n);
  for(int i=0;i<m;i++) if(!check[i]) U.merge(u[i],v[i]);
  long long ans=1LL*n*(n-1)/2;
  int used[n]{};
  for(int i=0;i<n;i++){
    if(used[U.root(i)]++) continue;
    ans-=1LL*U.size(i)*(U.size(i)-1)/2;
  }
  long long c[q];
  for(int i=q-1;i>=0;i--){
    c[i]=ans;
    if(!U.same(u[b[i]],v[b[i]])){
      ans-=1LL*U.size(u[b[i]])*U.size(v[b[i]]);
    }
    U.merge(u[b[i]],v[b[i]]);
  }
  for(int i=0;i<q;i++) cout<<c[i]<<endl;
}
0