結果

問題 No.416 旅行会社
ユーザー vjudge1
提出日時 2024-12-25 22:05:24
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,722 bytes
コンパイル時間 8,787 ms
コンパイル使用メモリ 276,340 KB
最終ジャッジ日時 2025-02-26 16:49:31
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
struct DSU {
    vector<int> fa, rank;
    DSU(int n) : fa(n), rank(n, 1) { iota(fa.begin(), fa.end(), 0); }
    int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) swap(x, y);
        fa[y] = x, rank[x] += rank[y];
    }
    bool same(int x, int y) { return find(x) == find(y); }
};
int main() {
    freopen("evacuate.in", "r", stdin);
    freopen("evacuate.out", "w", stdout);
    int n, m, q;
    cin >> n >> m >> q;
    set<pair<int, int>> edges;
    vector<int> ans(n, -1), rX(q), rY(q);
    vector<vector<int>> scc(n);
    DSU uf(n);

    for (int i = 0, x, y; i < m; i++) {
        cin >> x >> y;
        edges.emplace(x - 1, y - 1);
    }
    for (int i = 0; i < q; i++) {
        cin >> rX[i] >> rY[i];
        rX[i]--, rY[i]--, edges.erase({rX[i], rY[i]});
    }
    for (const auto& [x, y] : edges) uf.unite(x, y);
    for (int i = 0; i < n; i++) scc[uf.find(i)].push_back(i);
    for (int i = 0; i < n; i++)
        if (uf.same(0, i)) ans[i] = -1;
    for (int i = q - 1; i >= 0; i--) {
        int x = uf.find(rX[i]), y = uf.find(rY[i]);
        if (x != y) {
            if (uf.same(0, x))
                for (int node : scc[y]) ans[node] = i + 1;
            else if (uf.same(0, y))
                for (int node : scc[x]) ans[node] = i + 1;
            // merge
            if (scc[x].size() < scc[y].size()) swap(x, y);
            scc[x].insert(scc[x].end(), scc[y].begin(), scc[y].end());
            scc[y].clear();
            uf.unite(x, y);
        }
    }
    for (int i = 1; i < n; i++) cout << ans[i] << endl;
}
0