結果

問題 No.3200 Sinking Islands
コンテスト
ユーザー YY-otter
提出日時 2025-07-03 06:42:36
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 87 ms / 2,000 ms
コード長 2,329 bytes
コンパイル時間 1,234 ms
コンパイル使用メモリ 99,008 KB
実行使用メモリ 8,704 KB
最終ジャッジ日時 2025-07-03 16:51:53
合計ジャッジ時間 5,433 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>

struct DSU {
    std::vector<int> parent;
    std::vector<int> sz;
    DSU(int n) {
        parent.resize(n + 1);
        std::iota(parent.begin(), parent.end(), 0);
        sz.assign(n + 1, 1);
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            if (sz[root_i] < sz[root_j]) std::swap(root_i, root_j);
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
        }
    }
};

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

    int N, M;
    std::cin >> N >> M;
    std::vector<std::pair<int, int>> edges(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> edges[i].first >> edges[i].second;
    }

    int Q;
    std::cin >> Q;
    std::vector<int> query_edges(Q);
    std::vector<bool> is_removed(M, false);
    for (int i = 0; i < Q; ++i) {
        std::cin >> query_edges[i];
        query_edges[i]--; // 0-indexed
        is_removed[query_edges[i]] = true;
    }

    DSU dsu(N);
    for (int i = 0; i < M; ++i) {
        if (!is_removed[i]) {
            dsu.unite(edges[i].first, edges[i].second);
        }
    }

    long long current_disconnected_pairs = 0;
    std::vector<bool> visited_root(N + 1, false);
    long long connected_nodes = 0;
    for (int i = 1; i <= N; ++i) {
        int root = dsu.find(i);
        if (!visited_root[root]) {
            long long size = dsu.sz[root];
            current_disconnected_pairs += size * (N - connected_nodes - size);
            connected_nodes += size;
            visited_root[root] = true;
        }
    }

    std::vector<long long> ans(Q);
    for (int i = Q - 1; i >= 0; --i) {
        ans[i] = current_disconnected_pairs;
        
        int u = edges[query_edges[i]].first;
        int v = edges[query_edges[i]].second;
        int root_u = dsu.find(u);
        int root_v = dsu.find(v);

        if (root_u != root_v) {
            current_disconnected_pairs -= (long long)dsu.sz[root_u] * dsu.sz[root_v];
        }
        dsu.unite(u, v);
    }

    for (int i = 0; i < Q; ++i) {
        std::cout << ans[i] << "\n";
    }

    return 0;
}
0