# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
24680 | 2017-06-11T15:56:58 Z | Bruteforceman | Pipes (CEOI15_pipes) | C++11 | 1458 ms | 13792 KB |
#include "bits/stdc++.h" using namespace std; int *par; int *bic; int *subPar; int *subBic; vector <int> *g; int *low, *disc; bitset <100005> vis; vector <int> l, r; int rootPar(int x) { if(par[x] == x) return x; return par[x] = rootPar(par[x]); } int rootBic(int x) { if(bic[x] == x) return x; return bic[x] = rootBic(bic[x]); } void joinPar(int x, int y) { x = rootPar(x); y = rootPar(y); if(subPar[x] > subPar[y]) swap(x, y); if(x != y) { par[x] = y; subPar[y] += subPar[x]; } } void joinBic(int x, int y) { x = rootBic(x); y = rootBic(y); if(subBic[x] > subBic[y]) swap(x, y); if(x != y) { bic[x] = y; subBic[y] += subBic[x]; } } int tym; void dfs(int x, int parent) { vis[x] = 1; low[x] = disc[x] = ++tym; bool see = false; for(auto i : g[x]) { if (!see && i == parent) { see = true; continue; } if(vis[i] == 0) { dfs(i, x); low[x] = min(low[x], low[i]); if(disc[x] < low[i]) { l.push_back(x); r.push_back(i); } } else if (vis[i] == 1) { low[x] = min(low[x], disc[i]); } } } int main(int argc, char const *argv[]) { int n, m; scanf("%d %d", &n, &m); par = new int [n + 5]; bic = new int [n + 5]; subPar = new int [n + 5]; subBic = new int [n + 5]; for(int i = 1; i <= n; i++) { par[i] = i; bic[i] = i; subPar[i] = subBic[i] = 1; } for(int i = 1; i <= m; i++) { int p, q; scanf("%d %d", &p, &q); if(rootPar(p) != rootPar(q)) { joinPar(p, q); l.push_back(p); r.push_back(q); } else if (rootBic(q) != rootBic(p)) { joinBic(p, q); l.push_back(p); r.push_back(q); } } delete par; delete bic; delete subPar; delete subBic; g = new vector <int> [n + 5]; for(size_t i = 0; i < l.size(); i++) { g[l[i]].push_back(r[i]); g[r[i]].push_back(l[i]); } l.clear(); r.clear(); low = new int [n + 5]; disc = new int [n + 5]; for(int i = 1; i <= n; i++) { if(vis[i] == 0) { dfs(i, 0); } } for(size_t i = 0; i < l.size(); i++) { printf("%d %d\n", l[i], r[i]); } delete low; delete disc; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 896 KB | Output is correct |
2 | Correct | 6 ms | 768 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 116 ms | 760 KB | Output is correct |
2 | Correct | 113 ms | 632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 203 ms | 1712 KB | Output is correct |
2 | Correct | 238 ms | 1244 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 335 ms | 3556 KB | Output is correct |
2 | Correct | 288 ms | 3288 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 448 ms | 9876 KB | Output is correct |
2 | Correct | 393 ms | 6960 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 705 ms | 11204 KB | Output is correct |
2 | Correct | 695 ms | 8444 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 950 ms | 13792 KB | Output is correct |
2 | Correct | 912 ms | 9652 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1176 ms | 13780 KB | Output is correct |
2 | Correct | 1149 ms | 9700 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1458 ms | 13068 KB | Output is correct |
2 | Correct | 1423 ms | 10512 KB | Output is correct |