結果

問題 No.416 旅行会社
ユーザー yuriko32
提出日時 2025-07-08 01:05:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 403 ms / 4,000 ms
コード長 2,309 bytes
コンパイル時間 2,133 ms
コンパイル使用メモリ 209,108 KB
実行使用メモリ 26,372 KB
最終ジャッジ日時 2025-07-08 01:05:18
合計ジャッジ時間 7,751 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

vector<pair<int, int>> edges;  
vector<pair<int, int>> events;
vector<int> lost_power;        


vector<int> parent, size_set;

int find(int u) {
    return (parent[u] == u) ? u : find(parent[u]);
}
int findLevel(int u) {
    if(lost_power[u]!=0) return lost_power[u];
    else{
        if(parent[u] == u) return lost_power[u];
        else return findLevel(parent[u]);
    }
}

void union_sets(int u, int v) {
    int rootU = find(u);
    int rootV = find(v);
    if (rootU != rootV) {
        if (size_set[rootU] < size_set[rootV])
            swap(rootU, rootV);
        parent[rootV] = rootU;
        size_set[rootU] += size_set[rootV];
    }
}

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

    int N, M, Q;
    cin >> N >> M >> Q;

    parent.resize(N + 1);
    size_set.assign(N + 1, 1);
    lost_power.assign(N + 1, 0);

    for (int i = 1; i <= N; i++)
        parent[i] = i;

    set<pair<int, int>> removed_edges;
    for (int i = 0; i < M; i++) {
        int A, B;
        cin >> A >> B;
        edges.push_back({A, B});
    }

    for (int i = 0; i < Q; i++) {
        int C, D;
        cin >> C >> D;
        events.push_back({C, D});
        removed_edges.insert({C, D});
        removed_edges.insert({D, C});
    }


    for (auto [A, B] : edges) {
        if (!removed_edges.count({A, B})) {
            union_sets(A, B);
        }
    }

    vector<bool> has_power(N + 1, false);
    for (int i = 1; i <= N; i++) {
        if (find(i) == find(1)) {
            has_power[i] = true;
            lost_power[i]=-1;
        }
    }


    for (int event_id = Q; event_id >= 1; event_id--) {
        int C = events[event_id - 1].first;
        int D = events[event_id - 1].second;

        int x = find(C);
        int y = find(D);

        if (has_power[x] && has_power[y]) {
            union_sets(x, y);
            continue;
        }
        union_sets(x, y);
        if (find(x) == find(1) || find(y) == find(1)) {
            has_power[x] = has_power[y] = true;
            if (lost_power[x] == 0) lost_power[x] = event_id;
            if (lost_power[y] == 0) lost_power[y] = event_id;
        }
    }


    for (int i = 2; i <= N; i++) {
        cout << findLevel(i) << "\n";
    }

    return 0;
}
0