# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
460992 | 2021-08-09T11:46:20 Z | kingfran1907 | Potemkin cycle (CEOI15_indcyc) | C++14 | 1000 ms | 5500 KB |
#include <bits/stdc++.h> #define X first #define Y second using namespace std; typedef long long llint; const int maxn = 1010; const int base = 31337; const int mod = 1e9+7; const int inf = 0x3f3f3f3f; const int logo = 18; const int off = 1 << logo; const int treesiz = off << 1; int n, m; vector< int > graph[maxn]; int eg[maxn][maxn]; int dis[maxn]; queue< int > q; int main() { scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { int a, b; scanf("%d%d", &a, &b); graph[a].push_back(b); graph[b].push_back(a); eg[a][b] = eg[b][a] = 1; } for (int i = 1; i <= n; i++) { for (int j = 0; j < graph[i].size(); j++) { for (int k = j + 1; k < graph[i].size(); k++) { int x = graph[i][j]; int y = graph[i][k]; if (eg[x][y]) continue; for (int p = 1; p <= n; p++) dis[p] = inf; dis[i] = -1; for (int tren : graph[i]) dis[tren] = -1; dis[y] = inf; dis[x] = 0; q.push(x); while (!q.empty()) { int node = q.front(); q.pop(); for (int tren : graph[node]) { if (dis[tren] == inf) { dis[tren] = 1 + dis[node]; q.push(tren); } } } if (dis[y] == inf) continue; vector< int > v; int ptr = y; while (ptr != x) { v.push_back(ptr); for (int tren : graph[ptr]) { if (dis[tren] + 1 == dis[ptr]) { ptr = tren; break; } } } printf("%d %d ", i, x); reverse(v.begin(), v.end()); for (int i = 0; i < v.size(); i++) printf("%d ", v[i]); printf("\n"); return 0; } } } printf("no\n"); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 320 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 324 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 768 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 716 KB | Output is correct |
2 | Correct | 9 ms | 752 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 108 ms | 1540 KB | Output is correct |
2 | Correct | 2 ms | 1484 KB | Output is correct |
3 | Correct | 3 ms | 1612 KB | Output is correct |
4 | Correct | 111 ms | 1612 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1484 KB | Output is correct |
2 | Correct | 128 ms | 1560 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 449 ms | 4812 KB | Output is correct |
2 | Correct | 78 ms | 4684 KB | Output is correct |
3 | Execution timed out | 1091 ms | 5104 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 4556 KB | Output is correct |
2 | Execution timed out | 1079 ms | 4596 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 34 ms | 3072 KB | Output is correct |
2 | Correct | 126 ms | 3760 KB | Output is correct |
3 | Correct | 199 ms | 5500 KB | Output is correct |
4 | Execution timed out | 1063 ms | 5452 KB | Time limit exceeded |