# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
97139 | 2019-02-14T04:28:02 Z | dndhk | Pipes (CEOI15_pipes) | C++14 | 1579 ms | 12596 KB |
#include <iostream> #include <vector> #include <stdio.h> #include <algorithm> #define MAX_N 100000 using namespace std; int N, M; vector<int> gp[MAX_N+1]; int g1[MAX_N+1], g2[MAX_N+1]; int up[MAX_N+1], lv[MAX_N+1], p[MAX_N+1]; int find_g1(int x){ if(x==g1[x]) return x; return g1[x] = find_g1(g1[x]); } int find_g2(int x){ if(x==g2[x]) return x; return g2[x] = find_g2(g2[x]); } bool vst[MAX_N+1]; void dfs(int x){ bool tf = true; up[x] = lv[x]; vst[x] = true; for(int i=0; i<gp[x].size(); i++){ if(gp[x][i]==p[x] && tf){ tf = false; continue; } if(vst[gp[x][i]]){ up[x] = min(up[x], lv[gp[x][i]]); }else{ p[gp[x][i]] = x; lv[gp[x][i]] = lv[x]+1; dfs(gp[x][i]); if(up[gp[x][i]]>lv[x]){ printf("%d %d\n", gp[x][i], x); } up[x] = min(up[x], up[gp[x][i]]); } } } int main(){ scanf("%d %d", &N, &M); for(int i=1; i<=N; i++) g1[i] = g2[i] = i; int a, b; while(M--){ scanf("%d%d", &a, &b); if(find_g1(a)!=find_g1(b)){ gp[a].push_back(b); gp[b].push_back(a); a = find_g1(a); b = find_g1(b); g1[a] = b; } else if(find_g2(a)!=find_g2(b)){ gp[a].push_back(b); gp[b].push_back(a); a = find_g2(a); b = find_g2(b); g2[a] = b; } } for(int i=1; i<=N; i++){ if(!vst[i]){ lv[i] = 1; dfs(i); } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2688 KB | Output is correct |
2 | Correct | 4 ms | 2688 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 3072 KB | Output is correct |
2 | Correct | 8 ms | 2916 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 120 ms | 3020 KB | Output is correct |
2 | Correct | 131 ms | 2888 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 207 ms | 3676 KB | Output is correct |
2 | Correct | 243 ms | 3320 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 342 ms | 5012 KB | Output is correct |
2 | Correct | 292 ms | 4856 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 497 ms | 9684 KB | Output is correct |
2 | Correct | 421 ms | 7304 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 861 ms | 10704 KB | Output is correct |
2 | Correct | 783 ms | 8668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1094 ms | 12596 KB | Output is correct |
2 | Correct | 1050 ms | 9272 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1577 ms | 12552 KB | Output is correct |
2 | Correct | 1219 ms | 9300 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1579 ms | 11992 KB | Output is correct |
2 | Correct | 1425 ms | 10160 KB | Output is correct |