結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
![]() |
提出日時 | 2025-07-09 08:49:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 470 ms / 2,000 ms |
コード長 | 3,345 bytes |
コンパイル時間 | 2,988 ms |
コンパイル使用メモリ | 214,292 KB |
実行使用メモリ | 18,020 KB |
最終ジャッジ日時 | 2025-07-09 08:50:08 |
合計ジャッジ時間 | 14,126 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; class UnionFind { private: vector<int> _parents; vector<int> _size; int _vertexCount; public: UnionFind(int n) { _vertexCount = n; _parents.resize(n); _size.resize(n); for (int i = 0; i < n; i++) { _size[i] = 1; _parents[i] = i; } } int Root(int x) { if (_parents[x] == x) return x; return _parents[x] = Root(_parents[x]); } int Size(int x) { return _size[Root(x)]; } void Unite(int x, int y) { int rootX = Root(x); int rootY = Root(y); if (rootX == rootY) return; int from = rootX; int to = rootY; if (_size[from] > _size[to]) { swap(from, to); } _size[to] += _size[from]; _parents[from] = to; } vector<int> Find(int x) { int root = Root(x); vector<int> set; for (int i = 0; i < _vertexCount; i++) { if (Root(i) == root) { set.push_back(i); } } return set; } unordered_map<int, vector<int>> FindAll() { unordered_map<int, vector<int>> sets; for (int i = 0; i < _vertexCount; i++) { int root = Root(i); if (sets.find(root) != sets.end()) { sets[root].push_back(i); } else { sets.emplace(root, vector<int>()); sets[root].push_back(i); } } return sets; } bool Same(int x, int y) { int rootX = Root(x); int rootY = Root(y); return rootX == rootY; } void Clear() { for (int i = 0; i < _vertexCount; i++) { _parents[i] = i; _size[i] = 1; } } int VertexCount() { return _vertexCount; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N, M; cin >> N >> M; vector<pair<int, int>> edges; for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; u--; v--; if (u > v) { swap(u, v); } edges.emplace_back(u, v); } int Q; cin >> Q; vector<int> A(Q); set<int> setA; for (int i = 0; i < Q; i++) { cin >> A[i]; A[i]--; setA.insert(A[i]); } ll cur = (ll)N * (N - 1) / 2; UnionFind uf(N); for (int i = 0; i < M; i++) { if (setA.find(i) == setA.end()) { if (!uf.Same(edges[i].first, edges[i].second)) { cur -= (ll)uf.Size(edges[i].first) * uf.Size(edges[i].second); } uf.Unite(edges[i].first, edges[i].second); } } vector<ll> ans(Q); for (int i = 0; i < Q; i++) { ans[i] = cur; int u = edges[A[Q - i - 1]].first; int v = edges[A[Q - i - 1]].second; if (!uf.Same(u, v)) { cur -= (ll)uf.Size(u) * uf.Size(v); } uf.Unite(u, v); } reverse(ans.begin(), ans.end()); for (int i = 0; i < Q; i++) { cout << ans[i] << endl; } }