結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
|
提出日時 | 2025-07-11 21:44:23 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 563 ms / 2,000 ms |
コード長 | 778 bytes |
コンパイル時間 | 3,418 ms |
コンパイル使用メモリ | 292,592 KB |
実行使用メモリ | 17,280 KB |
最終ジャッジ日時 | 2025-07-11 21:44:39 |
合計ジャッジ時間 | 14,398 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; #include <atcoder/dsu> using atcoder::dsu; int main(){ ll n,m; cin>>n>>m; vector<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; vector<int> b(q); for(int i=0;i<q;i++)cin>>b[i],b[i]--; set<int> s; for(int i=0;i<q;i++)s.insert(b[i]); vector<ll> ans(q); dsu uf(n); ll now=n*(n-1)/2; for(int i=0;i<m;i++){ if(!s.count(i)){ int x=uf.leader(u[i]),y=uf.leader(v[i]); if(x!=y){ now-=uf.size(x)*(ll)uf.size(y); uf.merge(x,y); } } } for(int i=q-1;i>=0;i--){ ans[i]=now; int x=uf.leader(u[b[i]]),y=uf.leader(v[b[i]]); if(x!=y){ now-=uf.size(x)*(ll)uf.size(y); uf.merge(x,y); } } for(int i=0;i<q;i++)cout<<ans[i]<<endl; }