結果

問題 No.3200 Sinking Islands
ユーザー Rumain831
提出日時 2025-07-11 23:06:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,696 bytes
コンパイル時間 996 ms
コンパイル使用メモリ 89,952 KB
実行使用メモリ 10,448 KB
最終ジャッジ日時 2025-07-11 23:06:30
合計ジャッジ時間 10,204 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<int, int>;

struct UnionFind{
  vector<int> par, siz, rank;
  UnionFind(int n) : par(n, -1), siz(n, 1), rank(n, 1) {}  //メンバ変数をどのように初期化するかを表す
  //根を求めるやつ
  int root(int x){
    if(par[x]==-1) return x;
    else return par[x]=root(par[x]);
  }

  //xを含むグループとyを含むグループとを併合する
  bool unite(int x, int y){
    x=root(x); y=root(y);
    if(x==y) return false;
    if(rank[x]<rank[y]) swap(x, y);
    if(rank[x]==rank[y]) rank[x]++;
    par[y]=x;
    siz[x]+=siz[y];
    return true;
  }

  int size(int x){
    return siz[root(x)];
  }

};

int main(){
  int n, m; cin >> n >> m;
  vector<P> bri;
  for(int i=0; i<m; i++){
    int u, v; cin >> u >> v; u--, v--;
    bri.emplace_back(u, v);
  }
  int q; cin >> q;
  vector<int> cant(m), briidx;
  for(int i=0; i<q; i++){
    int b; cin >> b; b--;
    cant[b]++;
    briidx.push_back(b);
  }
  UnionFind uf(n);
  for(int i=0; i<m; i++) if(cant[i]==0){
    auto [u, v]=bri[i];
    uf.unite(u, v);
  }
  ll allpair=n*(n-1)/2, now=0;
  vector<ll> ans(q);
  vector<bool> checked(n, false);
  for(int i=0; i<n; i++){
    int p=uf.root(i);
    if(checked[p]) continue;
    ll k=uf.size(p);
    now+=k*(k-1)/2;
    checked[p]=true;
  }
  //cout << allpair-now << endl;
  for(int i=q-1; i>=0; i--){
    ans[i]=allpair-now;
    auto [u, v]=bri[briidx[i]];
    u=uf.root(u), v=uf.root(v);
    if(u==v) continue;
    ll p=uf.size(u), q=uf.size(v);
    now+=p*q;
    uf.unite(u, v);
  }
  for(auto p:ans) cout << p << endl;
  return 0;
}
0