# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
246563 | 2020-07-09T15:18:01 Z | dantoh000 | Potemkin cycle (CEOI15_indcyc) | C++14 | 547 ms | 8952 KB |
#include <bits/stdc++.h> using namespace std; int n,m; int id[1005][1005]; int A[1005]; int B[1005]; int vis[100005]; vector<int> ans; int cycle; bool dfs(int a, int b){ vis[id[a][b]] = 2; for (int c = 1; c <= n; c++){ if (c != a && id[b][c] && !id[a][c]){ if (vis[id[b][c]] == 2){ cycle = b; ans.push_back(b); ans.push_back(a); return true; } else if (dfs(b,c)){ ans.push_back(a); if (a == cycle){ int s = 0, e = ans.size()-1; for (int x = 0; x < ans.size(); x++){ for (int y = x+2; y < ans.size(); y++){ if (id[ans[x]][ans[y]] && e-s > y-x){ ///xxx illegal operation //printf("%d -> %d illegal \n",ans[x],ans[y]); /// just take from x to y instead, shorter cycle and guaranteed to be >3 from initial checks s = x, e = y; } } } for (int i = s; i <= e; i++) printf("%d ",ans[i]); exit(0); } return true; } } } vis[id[a][b]] = 1; return false; } int main(){ scanf("%d%d",&n,&m); for (int i = 1; i <= m; i++){ scanf("%d%d",&A[i],&B[i]); id[B[i]][A[i]] = id[A[i]][B[i]] = i; } for (int i = 1; i <= m; i++){ if (vis[i] == 0) { dfs(A[i],B[i]); ans.clear(); } } printf("no"); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 4 ms | 256 KB | Output is correct |
4 | Correct | 4 ms | 384 KB | Output is correct |
5 | Correct | 4 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 768 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 768 KB | Output is correct |
2 | Correct | 7 ms | 820 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 12 ms | 2944 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 1536 KB | Output is correct |
2 | Correct | 17 ms | 1536 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 547 ms | 8952 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 131 ms | 8568 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 40 ms | 4728 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |