結果
問題 | No.416 旅行会社 |
ユーザー |
|
提出日時 | 2016-08-26 23:11:40 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 633 ms / 4,000 ms |
コード長 | 3,006 bytes |
コンパイル時間 | 1,056 ms |
コンパイル使用メモリ | 79,596 KB |
実行使用メモリ | 15,468 KB |
最終ジャッジ日時 | 2024-12-14 19:49:33 |
合計ジャッジ時間 | 8,255 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include<iostream>#include<vector>#include<set>#define bgnE first#define endE secondusing 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;}