結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
![]() |
提出日時 | 2025-07-11 22:01:16 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 513 ms / 2,000 ms |
コード長 | 846 bytes |
コンパイル時間 | 3,648 ms |
コンパイル使用メモリ | 294,848 KB |
実行使用メモリ | 20,324 KB |
最終ジャッジ日時 | 2025-07-11 22:01:30 |
合計ジャッジ時間 | 14,423 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/dsu> using namespace std; int main(){ using ll=long long; ll n,m; cin>>n>>m; vector<pair<int,int>> edge(m); for (int i=0;i<m;i++){ int u,v; cin>>u>>v; u--;v--; edge[i]={u,v}; } int q; cin>>q; vector<int> b(q); vector<bool> use(m,true); for (int i=0;i<q;i++){ cin>>b[i]; b[i]--; use[b[i]]=false; } atcoder::dsu uf(n); for (int i=0;i<m;i++){ auto [u,v]=edge[i]; if (use[i]) uf.merge(u,v); } vector<ll> ans(q); ans[q-1]=n*(n-1)/2; for (auto v:uf.groups()){ ans[q-1]-=ll(v.size())*(v.size()-1)/2; } for (int i=q-1;i>=1;i--){ auto [u,v]=edge[b[i]]; ll cnt=0; if (!uf.same(u,v)){ cnt=ll(uf.size(u))*uf.size(v); uf.merge(u,v); } ans[i-1]=ans[i]-cnt; } for (int i=0;i<q;i++) cout<<ans[i]<<endl; }