結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
|
提出日時 | 2025-07-13 21:00:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 590 ms / 2,000 ms |
コード長 | 1,067 bytes |
コンパイル時間 | 5,714 ms |
コンパイル使用メモリ | 265,176 KB |
実行使用メモリ | 35,260 KB |
最終ジャッジ日時 | 2025-07-13 21:01:11 |
合計ジャッジ時間 | 17,085 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; #define int long long signed main(){ int N,M; cin >> N >> M; vector<pair<int,int>> bridge(M); for(int i = 0;i < M;i++){ int u,v; cin >> u >> v; u--,v--; if(u > v) swap(u,v); bridge[i].first = u; bridge[i].second = v; } int Q; cin >> Q; vector<int> col(Q); map<int,int> m; for(int i = 0;i < Q;i++){ cin >> col[i]; col[i]--; m[col[i]]++; } dsu d(N); for(int i = 0;i < M;i++){ if(m[i]) continue; d.merge(bridge[i].first,bridge[i].second); } int ans = N * (N-1)/2; auto gr = d.groups(); for(auto to : gr){ int n = (int)to.size(); ans -= n * (n-1)/2; } vector<int> vec; for(int i = Q-1;i >= 0;i--){ vec.push_back(ans); int d1 = d.size(bridge[col[i]].first); int d2 = d.size(bridge[col[i]].second); if(d.same(bridge[col[i]].first,bridge[col[i]].second))continue; else{ ans -= d1 * d2; d.merge(bridge[col[i]].first,bridge[col[i]].second); } } reverse(vec.begin(),vec.end()); for(auto to : vec) cout << to << endl; }