# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
154985 | 2019-09-25T19:24:33 Z | TadijaSebez | Pipes (CEOI15_pipes) | C++11 | 1788 ms | 14192 KB |
#include <bits/stdc++.h> using namespace std; #define pb push_back const int N=100050; const int H=2*N; const int M=4*N; struct DSU { int p[N]; DSU(){} int Find(int x){ return !p[x]?x:p[x]=Find(p[x]);} void Union(int x, int y){ p[Find(x)]=Find(y);} bool Same(int x, int y){ return Find(x)==Find(y);} } D1,D2; vector<int> E[N]; void AddEdge(int x, int y){ E[x].pb(y);E[y].pb(x);} int disc[N],low[N],par[N],tid; void DFS(int u) { disc[u]=low[u]=++tid; bool was=0; for(int v:E[u]) { if(v==par[u] && !was) { was=1; } else { if(!disc[v]) { par[v]=u; DFS(v); if(low[v]>disc[u]) printf("%i %i\n",u,v); low[u]=min(low[u],low[v]); } else low[u]=min(low[u],disc[v]); } } } int main() { int n,m,u,v; scanf("%i %i",&n,&m); for(int i=1;i<=m;i++) { scanf("%i %i",&u,&v); if(!D1.Same(u,v)) { D1.Union(u,v); AddEdge(u,v); } else if(!D2.Same(u,v)) { D2.Union(u,v); AddEdge(u,v); } } for(int i=1;i<=n;i++) if(!disc[i]) DFS(i); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 5 ms | 2680 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 3320 KB | Output is correct |
2 | Correct | 9 ms | 3064 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 144 ms | 3408 KB | Output is correct |
2 | Correct | 141 ms | 3320 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 245 ms | 4348 KB | Output is correct |
2 | Correct | 290 ms | 3932 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 406 ms | 5600 KB | Output is correct |
2 | Correct | 350 ms | 5640 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 606 ms | 10236 KB | Output is correct |
2 | Correct | 516 ms | 7468 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 883 ms | 11412 KB | Output is correct |
2 | Correct | 880 ms | 9088 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1194 ms | 13576 KB | Output is correct |
2 | Correct | 1109 ms | 9380 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1485 ms | 14192 KB | Output is correct |
2 | Correct | 1441 ms | 9376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1788 ms | 13164 KB | Output is correct |
2 | Correct | 1670 ms | 10684 KB | Output is correct |