結果

問題 No.3200 Sinking Islands
コンテスト
ユーザー joji
提出日時 2026-01-22 16:19:53
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 305 ms / 2,000 ms
コード長 4,042 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,554 ms
コンパイル使用メモリ 355,556 KB
実行使用メモリ 26,704 KB
最終ジャッジ日時 2026-01-22 16:20:06
合計ジャッジ時間 10,250 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#line 1 "3200.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/3200"
#line 2 "ds/unionfind/unionfind.hpp"
#include <algorithm>
#include <numeric>
#include <vector>

struct UnionFind {
        std::vector<int> parent, sz;
        int num_comps;
        UnionFind(int n = 0) { init(n); }
        void init(int n) {
                parent.resize(n);
                iota(parent.begin(), parent.end(), 0);
                sz.assign(n, 1);
                num_comps = n;
        }
        int find(int x) { return (x == parent[x] ? x : parent[x] = find(parent[x])); }
        bool same(int a, int b) { return find(a) == find(b); }
        int size(int x) { return sz[find(x)]; }
        bool join(int a, int b) {
                a = find(a), b = find(b);
                if (a != b) {
                        if (sz[a] < sz[b]) std::swap(a, b);
                        parent[b] = a;
                        sz[a] += sz[b];
                        num_comps--;
                        return true;
                }
                return false;
        }
        std::vector<std::vector<int>> groups() {
                int n = parent.size();
                std::vector<std::vector<int>> res(n);
                std::vector<int> group_size(n, 0);
                for (int i = 0; i < n; i++) {
                        group_size[find(i)]++;
                }
                std::vector<std::vector<int>> result;
                std::vector<int> root_map(n, -1);
                for (int i = 0; i < n; i++) {
                        int r = find(i);
                        if (root_map[r] == -1) {
                                root_map[r] = result.size();
                                result.push_back({});
                                result.back().reserve(group_size[r]);
                        }
                        result[root_map[r]].push_back(i);
                }
                return result;
        }
};
#line 3 "3200.test.cpp"
#include <bits/stdc++.h>
using namespace std;

void solve() {
        int64_t N, M;
        cin >> N >> M;
        UnionFind uf(N);
        vector<array<int, 2>> Edges(M);
        multiset<array<int, 2>> st;
        for (int i = 0; i < M; i++) {
                cin >> Edges[i][0] >> Edges[i][1];
                Edges[i][0]--, Edges[i][1]--;
                if (Edges[i][0] > Edges[i][1]) {
                        swap(Edges[i][0], Edges[i][1]);
                }
                st.insert({Edges[i][0], Edges[i][1]});
        }
        int Q;
        cin >> Q;
        vector<int> query(Q);
        for (int i = 0; i < Q; i++) {
                int num_edge;
                cin >> num_edge;
                num_edge--;
                query[i] = num_edge;
                auto it = st.find(Edges[num_edge]);
                st.erase(it);
        }
        vector<int64_t> ans;
        for (auto &[u, v] : st) {
                uf.join(u, v);
        }
        reverse(query.begin(), query.end());
        int64_t connected = 0, tot = N * (N - 1) / 2;
        auto group = uf.groups();
        for (auto &root : group) {
                int64_t now = (int64_t)root.size();
                connected += now * (now - 1) / 2;
        }
        for (auto &num_edge : query) {
                ans.push_back(tot - connected);
                int par1 = uf.find(Edges[num_edge][0]), par2 = uf.find(Edges[num_edge][1]);
                int64_t size1 = uf.sz[par1], size2 = uf.sz[par2];
                if (par1 != par2) {
                        connected -= (size1 * (size1 - 1) / 2 + size2 * (size2 - 1) / 2);
                        int64_t new_size = size1 + size2;
                        connected += new_size * (new_size - 1) / 2;
                }
                uf.join(par1, par2);
        }
        reverse(ans.begin(), ans.end());
        for (auto &x : ans) {
                cout << x << '\n';
        }
}

int main() {
        ios::sync_with_stdio(false);
        cin.tie(NULL);

        int t = 1;
        // cin >> t;
        while (t--) solve();

        return 0;
}
0