結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
|
提出日時 | 2025-07-11 22:54:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 649 ms / 2,000 ms |
コード長 | 1,806 bytes |
コンパイル時間 | 1,868 ms |
コンパイル使用メモリ | 152,980 KB |
実行使用メモリ | 23,856 KB |
最終ジャッジ日時 | 2025-07-11 22:54:38 |
合計ジャッジ時間 | 13,860 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <iostream> #include <vector> #include <cmath> #include <memory> #include <algorithm> #include <set> #include <map> #include <queue> #include <iomanip> #include <bitset> #include <string> #include <list> #include <deque> #include <stack> #include <limits> #include <numeric> #include <unordered_map> #include <unordered_set> #include <chrono> #include <random> // #include <atcoder/fenwicktree.hpp> #include <atcoder/segtree.hpp> // #include <atcoder/modint.hpp> #include <atcoder/dsu.hpp> using namespace atcoder; using namespace std; using ll = long long; using ull = unsigned long long; template <class T> using max_heap = priority_queue<T>; template <class T> using min_heap = priority_queue<T, vector<T>, greater<>>; ll ll_min = numeric_limits<ll>::min(); ll ll_max = numeric_limits<ll>::max(); ll ALPHABET_N = 26; static const ll INF = ll_min / 10; // using mint = modint1000000007; #define rep(i, n) for (ll i = (ll)0; i < (ll)n; i++) #define rep_(i, k, n) for (ll i = (ll)k; i < (ll)n; i++) #define all(a) a.begin(), a.end() int main() { ll n, m; cin >> n >> m; vector<ll> U(m), V(m); rep(i, m) cin >> U[i] >> V[i]; ll q; cin >> q; vector<ll> B(q); rep(i, q) { cin >> B[i]; B[i]--; } reverse(all(B)); vector<ll> ans; dsu d(n); set<ll> unused; rep(i, m) unused.insert(i); for (auto b : B) { unused.erase(b); } for (auto u : unused) { d.merge(U[u] - 1, V[u] - 1); } ll cur = n * (n - 1) / 2; for (auto g : d.groups()) { cur -= g.size() * (g.size() - 1) / 2; } for (auto b : B) { ans.push_back(cur); if (!d.same(U[b] - 1, V[b] - 1)) { ll size_u = d.size(U[b] - 1); ll size_v = d.size(V[b] - 1); cur -= size_u * size_v; d.merge(U[b] - 1, V[b] - 1); } } reverse(all(ans)); for (auto a : ans) { cout << a << endl; } return 0; }