# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
527420 | 2022-02-17T11:26:14 Z | maomao90 | Potemkin cycle (CEOI15_indcyc) | C++17 | 224 ms | 53968 KB |
#include <bits/stdc++.h> using namespace std; #define REP(i, j, k) for (int i = j; i < k; i++) #define RREP(i, j, k) for (int i = j; i >= k; i--) template<class T> inline bool mxto(T &a, T b) {return a < b ? a = b, 1 : 0;} template<class T> inline bool mnto(T &a, T b) {return a > b ? a = b, 1 : 0;} typedef long long ll; #define FI first #define SE second #define MP make_pair typedef pair<int, int> ii; #define pb push_back #define ALL(x) x.begin(), x.end() typedef vector<int> vi; typedef vector<ii> vii; #ifndef DEBUG #define cerr if (0) cerr #endif #define INF 1000000005 #define LINF 1000000000000000005ll #define MAXN 1005 #define MAXR 200005 int n, r; vi adj[MAXN], nadj[MAXR]; int grid[MAXN][MAXN]; ii eg[MAXR]; int vis[MAXR]; int p[MAXR]; bool done; void dfs(int u) { vis[u] = 2; for (int v : nadj[u]) { if (!vis[v]) { p[v] = u; dfs(v); if (done) { return; } } else if (vis[v] == 2) { vi tans; tans.pb(v); while (u != v) { assert(u != -1); tans.pb(u); u = p[u]; } vi ans; ans.pb(eg[tans[0]].SE); ans.pb(eg[tans[0]].FI); REP (i, 1, tans.size() - 1) { auto [a, b] = eg[tans[i]]; assert(a != ans.back()); assert(grid[ans.back()][a] != -1); ans.pb(a); } REP (i, 0, ans.size()) { assert(grid[ans[i]][ans[(i + 1) % ans.size()]] != -1); } assert(eg[tans.back()] == MP(ans[0], ans.back())); for (int i : ans) { cout << i << ' '; } cout << '\n'; done = 1; return; } } vis[u] = 1; } int main() { cout << "no\n"; #ifdef DEBUG ios::sync_with_stdio(0), cin.tie(0); #endif cin >> n >> r; memset(grid, -1, sizeof grid); REP (i, 0, r) { int a, b; cin >> a >> b; adj[a].pb(b); adj[b].pb(a); grid[a][b] = i; grid[b][a] = i + r; eg[i] = MP(a, b); eg[i + r] = MP(b, a); } REP (i, 0, 2 * r) { auto [a, b] = eg[i]; REP (j, 1, n + 1) { if (j == a) continue; if (grid[b][j] == -1) continue; if (grid[a][j] != -1) continue; nadj[i].pb(grid[b][j]); cerr << i << " --- " << grid[b][j] << '\n'; } } REP (i, 0, 2 * r) { if (vis[i]) continue; p[i] = -1; dfs(i); if (done) { return 0; } } cout << "no\n"; } /* 8 12 1 2 2 3 1 3 2 4 4 5 2 5 5 6 5 7 6 7 3 6 6 8 8 3 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 8908 KB | Expected integer, but "no" found |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 8908 KB | Expected integer, but "no" found |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 8908 KB | Expected integer, but "no" found |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 8908 KB | Expected integer, but "no" found |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 9164 KB | Expected integer, but "no" found |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 10 ms | 9328 KB | Extra information in the output file |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 10576 KB | Expected integer, but "no" found |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 224 ms | 25800 KB | Expected integer, but "no" found |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 106 ms | 53968 KB | Expected integer, but "no" found |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 122 ms | 12020 KB | Expected integer, but "no" found |
2 | Halted | 0 ms | 0 KB | - |