結果

問題 No.3200 Sinking Islands
コンテスト
ユーザー tanaka255
提出日時 2025-07-13 14:27:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 89 ms / 2,000 ms
コード長 2,017 bytes
コンパイル時間 2,622 ms
コンパイル使用メモリ 291,736 KB
実行使用メモリ 21,120 KB
最終ジャッジ日時 2025-07-13 14:28:05
合計ジャッジ時間 8,054 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
struct union_find{
  public:
    union_find(int n):_n(n),parent_or_size(n,-1){}
    int merge(int a,int b){
      int x=leader(a),y=leader(b);
      if(x==y)return x;
      if(-parent_or_size[x]<-parent_or_size[y])swap(x,y);
      parent_or_size[x]+=parent_or_size[y];
      parent_or_size[y]=x;
      return x;
    }
    int same(int a,int b){
      return leader(a)==leader(b);
    }
    int leader(int a){
      if(parent_or_size[a]<0)return a;
      return parent_or_size[a]=leader(parent_or_size[a]);
    }
    int size(int a){
      return -parent_or_size[leader(a)];
    }
    vector<vector<int>>groups(){
      vector<int>leader_buf(_n),group_size(_n);
      rep(i,_n){
        leader_buf[i]=leader(i);
        ++group_size[leader_buf[i]];
      }
      vector<vector<int>>result(_n);
      rep(i,_n)result[i].reserve(group_size[i]);
      rep(i,_n)result[leader_buf[i]].emplace_back(i);
      result.erase(
        remove_if(result.begin(),result.end(),[&](const vector<int>&v){
          return v.empty();
        }),
        result.end()
      );
      return result;
    }
  private:
    int _n;
    vector<int>parent_or_size;
};
int N,M,Q,B[2<<17];
pair<int,int>edges[2<<17];
bool down[2<<17];
signed main(){
  cin.tie(0)->sync_with_stdio(0);
  cin>>N>>M;
  rep(i,M){
    int u,v;cin>>u>>v,--u,--v;
    edges[i]={u,v};
  }
  cin>>Q;
  rep(i,Q){
    cin>>B[i],--B[i];
    down[B[i]]=1;
  }
  union_find uf(N);
  rep(i,M)if(!down[i])uf.merge(edges[i].first,edges[i].second);
  auto groups=uf.groups();
  ll ans=(ll)N*(N-1)/2;
  for(const vector<int>&g:groups){
    ll siz=g.size();
    ans-=siz*(siz-1)/2;
  }
  vector<ll>res={ans};
  for(int qi=Q-1;0<=qi;--qi){
    auto[u,v]=edges[B[qi]];
    if(!uf.same(u,v)){
      ans-=(ll)uf.size(u)*uf.size(v);
      uf.merge(u,v);
    }
    res.emplace_back(ans);
  }
  res.pop_back();
  reverse(res.begin(),res.end());
  for(auto&x:res)cout<<x<<'\n';
}
0