結果

問題 No.416 旅行会社
コンテスト
ユーザー vjudge1
提出日時 2024-12-25 22:05:24
言語 C++17(gcc12)
(gcc 12.4.0 + boost 1.90.0)
コンパイル:
g++-12 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
RE  
実行時間 -
コード長 1,722 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,549 ms
コンパイル使用メモリ 222,440 KB
実行使用メモリ 1,301,308 KB
最終ジャッジ日時 2026-07-06 10:03:42
合計ジャッジ時間 5,738 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 2 MLE * 4 -- * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:16:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   16 |     freopen("evacuate.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:17:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   17 |     freopen("evacuate.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#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