結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
|
提出日時 | 2025-07-03 06:42:36 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 87 ms / 2,000 ms |
コード長 | 2,329 bytes |
コンパイル時間 | 1,234 ms |
コンパイル使用メモリ | 99,008 KB |
実行使用メモリ | 8,704 KB |
最終ジャッジ日時 | 2025-07-03 16:51:53 |
合計ジャッジ時間 | 5,433 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <iostream> #include <vector> #include <numeric> struct DSU { std::vector<int> parent; std::vector<int> sz; DSU(int n) { parent.resize(n + 1); std::iota(parent.begin(), parent.end(), 0); sz.assign(n + 1, 1); } int find(int i) { if (parent[i] == i) return i; return parent[i] = find(parent[i]); } void unite(int i, int j) { int root_i = find(i); int root_j = find(j); if (root_i != root_j) { if (sz[root_i] < sz[root_j]) std::swap(root_i, root_j); parent[root_j] = root_i; sz[root_i] += sz[root_j]; } } }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int N, M; std::cin >> N >> M; std::vector<std::pair<int, int>> edges(M); for (int i = 0; i < M; ++i) { std::cin >> edges[i].first >> edges[i].second; } int Q; std::cin >> Q; std::vector<int> query_edges(Q); std::vector<bool> is_removed(M, false); for (int i = 0; i < Q; ++i) { std::cin >> query_edges[i]; query_edges[i]--; // 0-indexed is_removed[query_edges[i]] = true; } DSU dsu(N); for (int i = 0; i < M; ++i) { if (!is_removed[i]) { dsu.unite(edges[i].first, edges[i].second); } } long long current_disconnected_pairs = 0; std::vector<bool> visited_root(N + 1, false); long long connected_nodes = 0; for (int i = 1; i <= N; ++i) { int root = dsu.find(i); if (!visited_root[root]) { long long size = dsu.sz[root]; current_disconnected_pairs += size * (N - connected_nodes - size); connected_nodes += size; visited_root[root] = true; } } std::vector<long long> ans(Q); for (int i = Q - 1; i >= 0; --i) { ans[i] = current_disconnected_pairs; int u = edges[query_edges[i]].first; int v = edges[query_edges[i]].second; int root_u = dsu.find(u); int root_v = dsu.find(v); if (root_u != root_v) { current_disconnected_pairs -= (long long)dsu.sz[root_u] * dsu.sz[root_v]; } dsu.unite(u, v); } for (int i = 0; i < Q; ++i) { std::cout << ans[i] << "\n"; } return 0; }