結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
|
提出日時 | 2025-07-11 21:53:28 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 496 ms / 2,000 ms |
コード長 | 2,524 bytes |
コンパイル時間 | 4,841 ms |
コンパイル使用メモリ | 283,356 KB |
実行使用メモリ | 9,344 KB |
最終ジャッジ日時 | 2025-07-11 21:53:46 |
合計ジャッジ時間 | 12,884 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> #define fi first #define se second #define rep(i,s,n) for (int i = (s); i < (n); ++i) #define rrep(i,n,g) for (int i = (n)-1; i >= (g); --i) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define len(x) (int)(x).size() #define dup(x,y) (((x)+(y)-1)/(y)) #define pb push_back #define eb emplace_back #define Field(T) vector<vector<T>> using namespace std; using ll = long long; using ull = unsigned long long; template<typename T> using pq = priority_queue<T,vector<T>,greater<T>>; using P = pair<int,int>; template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;} template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;} class UnionFind { public: int n, cnt; vector <int> par; vector <int> siz; UnionFind(int sz_): n(sz_), cnt(sz_), par(sz_), siz(sz_, 1) { for (int i = 0; i < sz_; ++i) par[i] = i; } void init(int sz_) { n = sz_, cnt = sz_; par.resize(sz_); siz.assign(sz_, 1); for (int i = 0; i < sz_; ++i) par[i] = i; } int root(int x) { if (par[x] == x) { return x; } else { int r = root(par[x]); return par[x] = r; } } bool merge(int x, int y) { x = root(x); y = root(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; --cnt; return true; } bool is_same(int x, int y) { return root(x) == root(y); } int size(int x) { return siz[root(x)]; } int group_cnt() { return cnt; } vector<vector<int>> groups() { vector<vector<int>> ret(n); for (int i = 0; i < n; ++i) { ret[root(i)].emplace_back(i); } ret.erase(remove_if(ret.begin(), ret.end(), [](const vector<int> &v) { return v.empty(); }), ret.end()); return ret; } }; int main() { int n, m; cin >> n >> m; vector<int> u(m), v(m); rep(i,0,m) { cin >> u[i] >> v[i]; --u[i], --v[i]; } int q; cin >> q; vector<int> b(q), ch(m, 0); rep(i,0,q) { cin >> b[i]; --b[i]; ch[b[i]] = 1; } UnionFind uf(n); ll val = 1LL*n*(n-1)/2; rep(i,0,m) { if (!ch[i]) { if (!uf.is_same(u[i], v[i])) { val -= 1LL*uf.size(u[i])*uf.size(v[i]); uf.merge(u[i], v[i]); } } } vector<ll> ans(q); rrep(i,q,0) { ans[i] = val; if (!uf.is_same(u[b[i]], v[b[i]])) { val -= 1LL*uf.size(u[b[i]])*uf.size(v[b[i]]); uf.merge(u[b[i]], v[b[i]]); } } rep(i,0,q) { cout << ans[i] << endl; } return 0; }