# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
25730 | 2017-06-23T19:25:22 Z | gs14004 | Pipes (CEOI15_pipes) | C++11 | 490 ms | 14984 KB |
#include <cstdio> #include <vector> #include <algorithm> #include <cstring> using namespace std; typedef pair<int,int> pi; struct disj{ int pa[100005]; void init(int n){ for(int i=0; i<=n; i++) pa[i] = i; } int find(int x){ return pa[x] = (pa[x] == x ? x : find(pa[x])); } bool uni(int p, int q){ p = find(p); q = find(q); if(p == q) return 0; pa[q] = p; find(q); return 1; } }disj1, disj2; int n, m; vector<pi> bri; vector<int> graph[100005]; int par[100005][17], dep[100005]; bool vis[100005]; void dfs(int x, int pa){ vis[x] = 1; par[x][0] = pa; for (auto &i : graph[x]){ if(i == pa) continue; dep[i] = dep[x] + 1; dfs(i,x); } } int lca(int x, int y){ if(dep[x] < dep[y]) swap(x,y); int dx = dep[x] - dep[y]; for(int i=0; i<17; i++){ if((dx >> i) & 1) x = par[x][i]; } for(int i=16; i>=0; i--){ if(par[x][i] != par[y][i]){ x = par[x][i]; y = par[y][i]; } } if(x != y) x = par[x][0]; return x; } int up[100005]; void dfs2(int x, int pa){ vis[x] = 1; for (auto &i : graph[x]){ if(i == pa) continue; dfs2(i,x); up[x] = max(up[x], up[i] - 1); } if(pa != 0 && up[x] == 0) printf("%d %d\n",pa,x); } int main(){ scanf("%d %d\n",&n,&m); disj1.init(n); disj2.init(n); while(m--){ int u = 0, v = 0; char str[15]; fgets(str,15,stdin); int pos = 0; while(str[pos] != ' '){ u = (10 * u) + (str[pos] - '0'); pos++; } pos++; while(str[pos] != '\n' && str[pos]){ v = (10 * v) + (str[pos] - '0'); pos++; } if(disj1.uni(u,v)){ graph[u].push_back(v); graph[v].push_back(u); } else if(disj2.uni(u,v)){ bri.push_back(pi(u,v)); } } for(int i=1; i<=n; i++){ if(!vis[i]){ dfs(i,0); } } memset(vis, 0, sizeof(vis)); for(int i=1; i<17; i++){ for(int j=1; j<=n; j++){ par[j][i] = par[par[j][i-1]][i-1]; } } for(auto &i : bri){ int l = lca(i.first,i.second); up[i.first] = max(up[i.first],dep[i.first] - dep[l]); up[i.second] = max(up[i.second],dep[i.second] - dep[l]); } for(int i=1; i<=n; i++){ if(!vis[i]) dfs2(i, 0); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 2816 KB | Output is correct |
2 | Correct | 3 ms | 2816 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 3328 KB | Output is correct |
2 | Correct | 6 ms | 3328 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 34 ms | 3148 KB | Output is correct |
2 | Correct | 33 ms | 3136 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 54 ms | 4020 KB | Output is correct |
2 | Correct | 61 ms | 3992 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 108 ms | 5628 KB | Output is correct |
2 | Correct | 106 ms | 6220 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 202 ms | 11240 KB | Output is correct |
2 | Correct | 175 ms | 11248 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 276 ms | 12532 KB | Output is correct |
2 | Correct | 261 ms | 12272 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 367 ms | 14812 KB | Output is correct |
2 | Correct | 350 ms | 14984 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 424 ms | 14776 KB | Output is correct |
2 | Correct | 401 ms | 14852 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 490 ms | 14204 KB | Output is correct |
2 | Correct | 478 ms | 14496 KB | Output is correct |