# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
244462 | 2020-07-04T06:33:46 Z | dwsc | Potemkin cycle (CEOI15_indcyc) | C++14 | 1000 ms | 1400 KB |
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> ii; int n,m; vector<int> adj[1010]; int depth[1010],p[1010][10]; int lowest[1010][11]; int relabel[1010]; int counter; void dfs(int u,int pa){ //cout << u << pa << "hi\n"; depth[u] = depth[pa]+1; p[u][0] = pa; for (int i = 1; i <= 10; i++){ if (p[u][i-1] == 0) p[u][i] = 0; else p[u][i] = p[p[u][i-1]][i-1]; } for (int i = 0; i < adj[u].size(); i++){ int v = adj[u][i]; if (depth[v] != 0) continue; dfs(v,u); } relabel[u] = ++counter; } int lowestjump[1010]; int main(){ cin >> n >> m; for (int i = 0; i < m; i++){ int x,y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } for (int i = 1; i <= n; i++){ if (p[i][0] == 0) dfs(i,0); } vector<ii> backedges; for (int i = 1; i <= n; i++){ lowestjump[i] = 1e9; for (int j = 0; j < adj[i].size(); j++){ int ni = adj[i][j]; if (p[ni][0] == i || p[i][0] == ni) continue; if (depth[i] < depth[ni]) continue; lowestjump[i] = min(lowestjump[i],relabel[ni]); if (depth[i]-depth[ni] >= 3) backedges.push_back(ii(i,ni)); } } for (int i = 0; i < backedges.size(); i++){ int minjump = 1e9; int start = backedges[i].first, fin = backedges[i].second; if (lowestjump[start] != relabel[fin]) continue; int temp = start; while (temp != fin){ temp = p[temp][0]; minjump = min(minjump,lowestjump[temp]); } if (minjump <= relabel[fin]) continue; cout << start << " "; while (start != fin){ start = p[start][0]; cout << start << " "; } return 0; } cout << "no"; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 4 ms | 384 KB | Output is correct |
5 | Correct | 4 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1096 ms | 384 KB | Time limit exceeded |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1093 ms | 384 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1097 ms | 384 KB | Time limit exceeded |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1096 ms | 384 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1094 ms | 384 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1091 ms | 384 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1097 ms | 1016 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1094 ms | 640 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1092 ms | 1400 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |