# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
156371 | 2019-10-05T11:32:56 Z | Akashi | Potemkin cycle (CEOI15_indcyc) | C++14 | 440 ms | 2552 KB |
#include <bits/stdc++.h> using namespace std; int n, m; bool ad[1005][1005]; bool viz[1005]; int f[1005], TT[1005]; vector <int> v[1005]; vector <int> sol; queue <int> q; void find_path(int x, int y){ q.push(x); viz[y] = 0; while(!q.empty()){ int nod = q.front(); q.pop(); for(auto it : v[nod]) if(!viz[it]) viz[it] = 1, TT[it] = nod, q.push(it); } while(y != x){ sol.push_back(y); y = TT[y]; } sol.push_back(x); } bool find(int nod){ set <int> nodes; q.push(nod); while(!q.empty()){ int nod = q.front(); q.pop(); for(auto it : v[nod]){ if(!f[it]) f[it] = 3, q.push(it); if(f[it] == 2) nodes.insert(it); } } for(auto x : nodes){ for(auto y : nodes){ if(!ad[x][y] && x != y){ find_path(x, y); return 1; } } } return 0; } bool solve(int nod){ f[nod] = 1; viz[nod] = 1; for(auto it : v[nod]) viz[it] = 1, f[it] = 2; for(int i = 1; i <= n ; ++i) if(!f[i]){ f[i] = 3; if(find(i)) return 1; } return 0; } int main() { // freopen("1.in", "r", stdin); scanf("%d%d", &n, &m); int x, y; for(int i = 1; i <= m ; ++i){ scanf("%d%d", &x, &y); v[x].push_back(y); v[y].push_back(x); ad[x][y] = ad[y][x] = 1; } for(int i = 1; i <= n ; ++i){ sol.push_back(i); memset(f, 0, sizeof(f)); memset(viz, 0, sizeof(viz)); if(solve(i)) break ; sol.pop_back(); } if(sol.size() == 0) printf("no"); else for(auto it : sol) printf("%d ", it); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 504 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 504 KB | Output is correct |
2 | Correct | 4 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 736 KB | Output is correct |
2 | Correct | 3 ms | 632 KB | Output is correct |
3 | Correct | 4 ms | 760 KB | Output is correct |
4 | Correct | 17 ms | 760 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 760 KB | Output is correct |
2 | Correct | 16 ms | 760 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 1912 KB | Output is correct |
2 | Correct | 10 ms | 1656 KB | Output is correct |
3 | Correct | 257 ms | 1916 KB | Output is correct |
4 | Correct | 112 ms | 1656 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 1656 KB | Output is correct |
2 | Correct | 296 ms | 1796 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 1784 KB | Output is correct |
2 | Correct | 25 ms | 1784 KB | Output is correct |
3 | Correct | 34 ms | 2040 KB | Output is correct |
4 | Correct | 440 ms | 2552 KB | Output is correct |