結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
|
提出日時 | 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 |
ソースコード
#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'; }