結果

問題 No.416 旅行会社
ユーザー HachimoriHachimori
提出日時 2016-08-26 23:11:40
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 550 ms / 4,000 ms
コード長 3,006 bytes
コンパイル時間 980 ms
コンパイル使用メモリ 79,920 KB
実行使用メモリ 15,584 KB
最終ジャッジ日時 2024-05-08 14:57:31
合計ジャッジ時間 7,128 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 274 ms
11,904 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 8 ms
5,376 KB
testcase_09 AC 31 ms
5,376 KB
testcase_10 AC 285 ms
12,188 KB
testcase_11 AC 282 ms
12,324 KB
testcase_12 AC 289 ms
12,320 KB
testcase_13 AC 271 ms
11,776 KB
testcase_14 AC 545 ms
15,468 KB
testcase_15 AC 534 ms
15,468 KB
testcase_16 AC 526 ms
15,468 KB
testcase_17 AC 535 ms
15,584 KB
testcase_18 AC 550 ms
15,460 KB
testcase_19 AC 392 ms
15,496 KB
testcase_20 AC 393 ms
15,300 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<set>
#define bgnE first
#define endE second
using namespace std;
const int BUF = 100005;
typedef pair<int, int> Edge;


class DisjointSet {
private:
    int node2group[BUF];
    vector<vector<int> > group2node;

public:
    DisjointSet() {}
    
    DisjointSet(int n) {
        group2node = vector< vector<int> >(n);
        
        for (int i = 0; i < n; ++i) {
            node2group[i] = i;
            group2node[i].push_back(i);
        }
    }

    void merge(int a, int b) {
        if (find(a) != find(b)) {
            vector<int> &groupA = findGroup(a);
            vector<int> &groupB = findGroup(b);

            if (groupA.size() < groupB.size()) {
                while (!groupA.empty()) {
                    groupB.push_back(groupA.back());
                    groupA.pop_back();
                }
                node2group[find(a)] = find(b);
            }
            else {
                while (!groupB.empty()) {
                    groupA.push_back(groupB.back());
                    groupB.pop_back();
                }
                node2group[find(b)] = find(a);
            }
        }
    }

    int find(int a) {
        if (node2group[a] == a) return a;
        return node2group[a] = find(node2group[a]);
    }

    vector<int>& findGroup(int a) {
        return group2node[find(a)];
    }
};


int nNode;
set<Edge> availEdges;
vector<Edge> removeEdgeOrder;

void read() {
    availEdges.clear();
    removeEdgeOrder.clear();

    int nEdge, nQuery;
    cin >> nNode >> nEdge >> nQuery;

    for (int i = 0; i < nEdge; ++i) {
        int s, t;
        cin >> s >> t;
        --s;
        --t;
        availEdges.insert(Edge(s, t));
    }

    for (int i = 0; i < nQuery; ++i) {
        int s, t;
        cin >> s >> t;
        --s;
        --t;
        availEdges.erase(Edge(s, t));
        removeEdgeOrder.push_back(Edge(s, t));
    }
}


void work() {
    static DisjointSet dset;
    dset = DisjointSet(nNode);

    for (set<Edge>::iterator it = availEdges.begin(); it != availEdges.end(); ++it) {
        Edge edge = *it;
        dset.merge(edge.bgnE, edge.endE);
    }

    static int ans[BUF];
    for (int i = 0; i < nNode; ++i) {
        if (dset.find(0) == dset.find(i)) {
            ans[i] = -1;
        }
    }

    for (int i = removeEdgeOrder.size() - 1; i >= 0; --i) {
        Edge &addEdge = removeEdgeOrder[i];

        if (dset.find(0) == dset.find(addEdge.endE)) {
            swap(addEdge.bgnE, addEdge.endE);
        }

        if (dset.find(0) == dset.find(addEdge.bgnE) && dset.find(0) != dset.find(addEdge.endE)) {
            vector<int> &joinedGroup = dset.findGroup(addEdge.endE);
            for (int j = 0; j < joinedGroup.size(); ++j) {
                ans[joinedGroup[j]] = i + 1;
            }
        }
        dset.merge(addEdge.bgnE, addEdge.endE);
    }

    for (int i = 1; i < nNode; ++i) {
        cout << ans[i] << endl;
    }
}


int main() {
    read();
    work();
    return 0;
}
0