# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
44868 | 2018-04-08T20:08:25 Z | bogdan10bos | Pipes (CEOI15_pipes) | C++14 | 710 ms | 65536 KB |
#include <bits/stdc++.h> using namespace std; //#define FILE_IO typedef pair<int, int> pii; int N, M; int K, vis[100005], lst[100005]; vector<int> nodes, edg[100005]; vector<pii> critical; queue<pii> q; class UnionFind { public: int N; int f[100005]; void init(int _N) { N = _N; for(int i = 1; i <= N; i++) f[i] = i; } int F(int x) { if(f[x] == x) return x; return f[x] = F(f[x]); } void unite(int x, int y) { if(F(x) == F(y)) return; f[F(y)] = F(x); } }; UnionFind f[2]; int main() { #ifdef FILE_IO freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); #endif scanf("%d%d", &N, &M); f[0].init(N), f[1].init(N); for(int i = 1; i <= M; i++) { int x, y; scanf("%d%d", &x, &y); if(f[0].F(x) != f[0].F(y)) { critical.push_back({x, y}); f[0].unite(x, y); int fx = f[1].F(x); int fy = f[1].F(y); edg[fx].push_back(fy); edg[fy].push_back(fx); continue; } if(f[1].F(x) == f[1].F(y)) continue; x = f[1].F(x); y = f[1].F(y); nodes.clear(); nodes.push_back(x); nodes.push_back(y); while(!q.empty()) q.pop(); K += 2; vis[x] = K; vis[y] = K + 1; q.push({x, K}); q.push({y, K + 1}); while(!q.empty()) { int nod = q.front().first; int id = q.front().second; q.pop(); for(auto nxt: edg[nod]) { if(vis[nxt] == id) continue; if(vis[nxt] == (id ^ 1)) { int nd1 = nod; int nd2 = nxt; if(vis[nod] != K) swap(nd1, nd2); while(nd1 != x) { nodes.push_back(nd1); nd1 = lst[nd1]; } while(nd2 != y) { nodes.push_back(nd2); nd2 = lst[nd2]; } while(!q.empty()) q.pop(); break; } vis[nxt] = vis[nod]; lst[nxt] = nod; } } for(int i = 1; i < nodes.size(); i++) { f[1].unite(nodes[0], nodes[i]); for(auto x: edg[ nodes[i] ]) if(f[1].F(x) != f[1].F(nodes[0])) edg[ nodes[0] ].push_back(x); } } for(auto e: critical) if(f[1].F(e.first) != f[1].F(e.second)) printf("%d %d\n", e.first, e.second); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 2688 KB | Wrong number of edges |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 6144 KB | Wrong number of edges |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 116 ms | 5656 KB | Output is correct |
2 | Correct | 110 ms | 3404 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 246 ms | 21280 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 510 ms | 41812 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 578 ms | 65536 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 612 ms | 65536 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 710 ms | 65536 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 691 ms | 65536 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 674 ms | 65536 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |