結果

問題 No.416 旅行会社
ユーザー pekempey
提出日時 2016-08-26 22:43:31
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 311 ms / 4,000 ms
コード長 1,440 bytes
コンパイル時間 1,614 ms
コンパイル使用メモリ 172,888 KB
実行使用メモリ 14,976 KB
最終ジャッジ日時 2024-12-14 19:44:42
合計ジャッジ時間 5,626 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:40:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |                 scanf("%d %d", &a, &b);
      |                 ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:47:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   47 |                 scanf("%d %d", &c[i], &d[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
    vector<int> parent;
    vector<vector<int>> group;
    UnionFind(int n) : parent(n), group(n) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            group[i].push_back(i);
        }
    }
    int operator[](int x) {
        if (parent[x] == x) return x;
        return parent[x] = operator[](parent[x]);
    }
    bool merge(int x, int y) {
        x = operator[](x);
        y = operator[](y);
        if (x == y) return false;
        if (x > y) swap(x, y);
        if (group[x].size() < group[y].size()) swap(group[x], group[y]);
        for (int e : group[y]) group[x].push_back(e);
        parent[y] = x;
        return true;
    }
};
int main() {
    int n, m, q;
    cin >> n >> m >> q;
    set<pair<int, int>> g;
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        g.emplace(minmax(a, b));
    }
    vector<int> c(q), d(q);
    for (int i = 0; i < q; i++) {
        scanf("%d %d", &c[i], &d[i]);
        c[i]--; d[i]--;
        g.erase(minmax(c[i], d[i]));
    }
    UnionFind uf(n);
    for (auto e : g) {
        uf.merge(e.first, e.second);
    }
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        if (uf[0] == uf[i]) {
            ans[i] = -1;
        }
    }
    for (int i = q - 1; i >= 0; i--) {
        c[i] = uf[c[i]];
        d[i] = uf[d[i]];
        if (c[i] > d[i]) swap(c[i], d[i]);
        if (c[i] != d[i]) {
            if (c[i] == 0) {
                for (int e : uf.group[d[i]]) {
                    ans[e] = i + 1;
                }
            }
            uf.merge(c[i], d[i]);
        }
    }
    for (int i = 1; i < n; i++) {
        printf("%d\n", ans[i]);
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0