Submission #36939

#TimeUsernameProblemLanguageResultExecution timeMemory
36939aomePotemkin cycle (CEOI15_indcyc)C++14
100 / 100
223 ms8100 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1005; int n, m; int nxt[N][N]; int par[N]; bool E[N][N]; bool finish[N][N]; vector<int> go; void cal(int x, int y) { vector<int > vx, vy; while (par[x] != x) vx.push_back(x), x = par[x]; vx.push_back(x); while (par[y] != y) vy.push_back(y), y = par[y]; reverse(vy.begin(), vy.end()); for (auto i : vy) vx.push_back(i); for (auto i : vx) cout << i << ' '; } void trace() { int sz = go.size(); for (auto i : go) par[i] = 0; queue<int> qu; par[go[0]] = go[0], qu.push(go[0]); while (qu.size()) { int u = qu.front(); qu.pop(); for (auto v : go) { if (!E[u][v]) continue; if (!par[v]) { par[v] = u, qu.push(v); } else if (par[u] != v) { cal(u, v); exit(0); } } } } void dfs(int x, int y) { for (int i = 1; i <= n; ++i) { if (!E[y][i] || E[x][i]) continue; if (nxt[y][i] < 0 || finish[y][i]) continue; if (nxt[y][i] > 0) { int curx = x, cury = y; while (curx != y && cury != i) { go.push_back(cury); int tmp = nxt[curx][cury]; cury = curx, curx = tmp; } go.push_back(cury), trace(); } else nxt[y][i] = x, nxt[i][y] = -x, dfs(y, i); } finish[x][y] = finish[y][x] = 1; } int main() { ios::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; E[u][v] = E[v][u] = 1; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (!E[i][j] || nxt[i][j]) continue; nxt[i][j] = i, nxt[j][i] = -i, E[j][i] = 0, dfs(i, j); } } cout << "no"; }

Compilation message (stderr)

indcyc.cpp: In function 'void trace()':
indcyc.cpp:24:6: warning: unused variable 'sz' [-Wunused-variable]
  int sz = go.size();
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...