結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
![]() |
提出日時 | 2025-07-11 22:18:01 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 264 ms / 2,000 ms |
コード長 | 1,760 bytes |
コンパイル時間 | 5,845 ms |
コンパイル使用メモリ | 334,456 KB |
実行使用メモリ | 21,252 KB |
最終ジャッジ日時 | 2025-07-11 22:18:15 |
合計ジャッジ時間 | 12,092 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#if __has_include(<yoniha/all.h>) #include <yoniha/all.h> using namespace atcoder; #else #include <bits/stdc++.h> #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; #endif #endif using namespace std; #define int long long #define all(x) (x).begin(), (x).end() #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for(int i = (int)(n - 1); i >= 0; i--) template <typename T> bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template <typename T> bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;} // using mint = modint; signed main(){ int n, m; cin >> n >> m; vector<pair<int, int>> uv(m); for(auto&& [u, v] : uv) cin >> u >> v, u--, v--; int q; cin >> q; vector<int> b(q); vector uv_default(m, true); // 最初からある辺はtrue for(auto&& bi : b){ cin >> bi; bi--; uv_default.at(bi) = false; } dsu d(n); rep(i, m) if(uv_default.at(i)){ auto [u, v] = uv.at(i); d.merge(u, v); } int size_sq_sum = 0; auto vv = d.groups(); for(const auto& v : vv) size_sq_sum += v.size() * v.size(); vector<int> ans(q); rrep(i, q){ ans.at(i) = (n * n - size_sq_sum) / 2; auto [u, v] = uv.at(b.at(i)); if(!d.same(u, v)){ int size_u = d.size(u), size_v = d.size(v), size_after = size_u + size_v; size_sq_sum -= size_u * size_u + size_v * size_v; size_sq_sum += size_after * size_after; } d.merge(u, v); } for(auto i : ans) cout << i << '\n'; } /* 逆順に辺を追加していく 答えは、(各連結成分のsize * (n - size)の総和)/2 sum(size * (n - size)) = n * n - sum(size * size); 例えば、 1 1 1 1 1→2 1 1 1のとき、 答えは 10→9 n=5 6+4+4+4 */