| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 244531 |
2020-07-04T09:18:21 Z |
shenxy |
Pipes (CEOI15_pipes) |
C++11 |
|
1805 ms |
6624 KB |
//happy birthday errorgorn
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef pair<int, int> ii;
struct UFDS {
vector<int> parent, rankof;
UFDS(int N) {
for (int i = 0; i < N; ++i) parent.push_back(i), rankof.push_back(1);
}
int find_parent(int i) {
if (parent[i] == i) return i;
return parent[i] = find_parent(parent[i]);
}
void merge(int p, int q) {
p = find_parent(p), q = find_parent(q);
if (p == q) return;
if (rankof[p] > rankof[q]) parent[q] = p, rankof[p] += rankof[q];
else parent[p] = q, rankof[q] += rankof[p];
}
};
struct UFDSpp {
vector<int> parent, rankof, root;
UFDSpp(int N) {
for (int i = 0; i < N; ++i) parent.push_back(i), rankof.push_back(0), root.push_back(i);
}
int find_parent(int i) {
if (parent[i] == i) return i;
return parent[i] = find_parent(parent[i]);
}
int get_root(int i) {
return root[find_parent(i)];
}
void merge(int p, int q) {
p = find_parent(p), q = find_parent(q);
if (p == q) return;
if (rankof[p] == rankof[q]) ++rankof[p];
if (rankof[p] > rankof[q]) parent[q] = p;
else root[q] = root[p], parent[p] = q;
}
};
struct BridgeTree {
map<int, ii> bridges;
UFDS* cc;
UFDSpp* bridgecc;
vector<ii> parent;
vector<char> visited;
BridgeTree(int N) {
cc = new UFDS(N);
bridgecc = new UFDSpp(N);
for (int i = 0; i < N; ++i) parent.push_back(ii(-1, -1));
for (int i = 0; i < N; ++i) visited.push_back(0);
}
void add_edge(int id, int a, int b) {
if (cc -> find_parent(a) != cc -> find_parent(b)) {
if (cc -> rankof[cc -> find_parent(a)] > cc -> rankof[cc -> find_parent(b)]) swap(a, b);
ii p1 = ii(-1, -1), p2 = ii(-1, -1);
int i;
for (i = bridgecc -> get_root(a); parent[i].first != -1; i = bridgecc -> get_root(parent[i].first)) {
if (p2.first != -1) parent[p1.first] = p2;
p2 = p1;
p1 = ii(i, parent[i].second);
}
if (p2.first != -1) parent[p1.first] = p2;
if (p1.first != -1) parent[i] = p1;
parent[bridgecc -> get_root(a)] = ii(bridgecc -> get_root(b), id);
cc -> merge(a, b);
bridges[id] = ii(a, b);
} else if (bridgecc -> find_parent(a) != bridgecc -> find_parent(b)) {
int p = bridgecc -> get_root(a), q = bridgecc -> get_root(b), lca;
while (true) {
if (visited[p] == 2) {
lca = p;
break;
} else visited[p] = 1;
if (visited[q] == 1) {
lca = q;
break;
} else visited[q] = 2;
if (parent[p].first != -1) p = bridgecc -> get_root(parent[p].first);
if (parent[q].first != -1) q = bridgecc -> get_root(parent[q].first);
}
for (int i = bridgecc -> get_root(a); i != lca; i = bridgecc -> get_root(parent[i].first)) {
visited[i] = 0;
bridges.erase(parent[i].second);
bridgecc -> merge(lca, i);
}
for (int i = bridgecc -> get_root(b); i != lca; i = bridgecc -> get_root(parent[i].first)) {
visited[i] = 0;
bridges.erase(parent[i].second);
bridgecc -> merge(lca, i);
}
for (int i = lca; i != -1 && visited[i]; i = parent[i].first == -1 ? -1 : bridgecc -> get_root(parent[i].first)) visited[i] = 0;
}
}
};
int main() {
int N, M, u, v;
scanf("%d %d", &N, &M);
BridgeTree bride(N);
for (int i = 0; i < M; ++i) {
scanf("%d %d", &u, &v);
bride.add_edge(i, u - 1, v - 1);
}
for (auto i: bride.bridges) printf("%d %d\n", i.second.first + 1, i.second.second + 1);
return 0;
}
Compilation message
pipes.cpp: In function 'int main()':
pipes.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
640 KB |
Output is correct |
| 2 |
Correct |
10 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
512 KB |
Output is correct |
| 2 |
Correct |
147 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
258 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
298 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
410 ms |
1916 KB |
Output is correct |
| 2 |
Correct |
357 ms |
2036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
549 ms |
4796 KB |
Output is correct |
| 2 |
Correct |
495 ms |
4572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
868 ms |
5360 KB |
Output is correct |
| 2 |
Correct |
838 ms |
5016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1216 ms |
6624 KB |
Output is correct |
| 2 |
Correct |
1104 ms |
6492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1497 ms |
6516 KB |
Output is correct |
| 2 |
Correct |
1368 ms |
6492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1805 ms |
6260 KB |
Output is correct |
| 2 |
Correct |
1654 ms |
6240 KB |
Output is correct |
