結果
問題 |
No.3200 Sinking Islands
|
ユーザー |
![]() |
提出日時 | 2025-07-11 22:23:54 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 359 ms / 2,000 ms |
コード長 | 5,285 bytes |
コンパイル時間 | 4,516 ms |
コンパイル使用メモリ | 283,824 KB |
実行使用メモリ | 11,632 KB |
最終ジャッジ日時 | 2025-07-11 22:24:06 |
合計ジャッジ時間 | 10,872 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
// #pragma GCC target("avx") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; using std::cin; using std::cout; #define rep(i,n) for(int i = 0; i < (int)n; i++) #define FOR(n) for(int i = 0; i < (int)n; i++) #define repi(i,a,b) for(int i = (int)a; i < (int)b; i++) #define all(x) x.begin(),x.end() //#define mp make_pair #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define vvvvi vector<vvvi> #define pii pair<int,int> #define vpii vector<pair<int,int>> template<typename T> bool chmax(T &a, const T b) {if(a<b) {a=b; return true;} else {return false;}} template<typename T> bool chmin(T &a, const T b) {if(a>b) {a=b; return true;} else {return false;}} using ll = long long; using ld = long double; using ull = unsigned long long; const ll INF = numeric_limits<long long>::max() / 2; const ld pi = 3.1415926535897932384626433832795028; const ll mod = 998244353; int dx[] = {1, 0, -1, 0, -1, -1, 1, 1}; int dy[] = {0, 1, 0, -1, -1, 1, -1, 1}; #define int long long struct UnionFind { vector<int> r; UnionFind() = default; UnionFind(int n) { r = vector<int>(n, -1); } int root(int x) { if(r[x] < 0) return x; return r[x] = root(r[x]); } bool unite(int x, int y) { x = root(x); y = root(y); if(x == y) return false; if(r[x] > r[y]) swap(x, y); r[x] += r[y]; r[y] = x; return true; } bool issame(int x, int y) { return root(x) == root(y); } int size(int x) { return -r[root(x)]; } bool all_connected() { return size(0) == (int)r.size(); } // // not debugged // vector<int> get_component(int x) { // int cur = x; // vector<int> ret = {cur}; // cur = nxt[cur]; // while (cur != x) { // ret.emplace_back(cur); // cur = nxt[cur]; // } // return ret; // } // int number_of_set() { // unordered_set<int> st; // for(int i = 0; i < (int)r.size(); i++) st.insert(root(i)); // return st.size(); // } // only vertices: not including leader pos // vector<vector<int>> decompose() { // vector<pair<int, int>> p; // p.reserve((int)r.size()); // for(int i = 0; i < (int)r.size(); i++) p.emplace_back(root(i), i); // sort(all(p)); // //first:root, second:vertices // vector<vector<int>> ret; // int pre = -1; // for(pair<int, int> e : p) { // if(pre != e.first) { // ret.push_back(vector<int>{e.second}); // }else { // ret.back().push_back(e.second); // } // pre = e.first; // } // return ret; // } // leader and groups vertex // vector<pair<int, vector<int>>> decompose() { // vector<pair<int, int>> p; // for(int i = 0; i < (int)r.size(); i++) p.emplace_back(root(i), i); // sort(all(p)); // //first:root, second:vertices // vector<pair<int, vector<int>>> ret; // int pre = -1; // for(pair<int, int> e : p) { // if(pre != e.first) { // ret.push_back(make_pair(e.first, vector<int>{e.second})); // }else { // ret.back().second.push_back(e.second); // } // pre = e.first; // } // return ret; // } // vector<int> roots(vector<int> x) { // vector<int> ret((int)x.size()); // for(int i = 0; i < (int)x.size(); i++) ret[i] = root(i); // return ret; // } // bool unite(pair<int, int> p) { // return unite(p.first, p.second); // } // vector<bool> unite(vector<pair<int, int>> p) { // vector<bool> ret((int)p.size()); // for(int i = 0; i < (int)p.size(); i++) { // ret[i] = unite(p[i]); // } // return ret; // } // vector<bool> unite(vector<int> x, vector<int> y) { // assert(x.size() == y.size()); // vector<bool> ret((int)x.size()); // for(int i = 0; i < (int)x.size(); i++) { // ret[i] = unite(x[i], y[i]); // } // return ret; // } // bool issame(pair<int, int> p) { // return issame(p.first, p.second); // } }; void solve() { int n, m; cin >> n >> m; vi u(m), v(m); FOR(m) { cin >> u[i] >> v[i]; u[i]--; v[i]--; } vector<bool> will_fall(m, false); int q; cin >> q; vi b(q); FOR(q) cin >> b[i], b[i]--, will_fall[b[i]] = true; int ans = n * (n - 1) / 2; UnionFind UF(n); FOR(m) if (!will_fall[i] && !UF.issame(u[i], v[i])) { ans -= UF.size(u[i]) * UF.size(v[i]); UF.unite(u[i], v[i]); } vi answers; for (int i = q-1; i >= 0; i--) { answers.emplace_back(ans); if (!UF.issame(u[b[i]], v[b[i]])) { ans -= UF.size(u[b[i]]) * UF.size(v[b[i]]); UF.unite(u[b[i]], v[b[i]]); } } reverse(all(answers)); FOR(q) cout << answers[i] << endl; } signed main() { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); return 0; }