Submission #53902

#TimeUsernameProblemLanguageResultExecution timeMemory
53902paulicaPotemkin cycle (CEOI15_indcyc)C++14
100 / 100
78 ms4076 KiB
#include <bits/stdc++.h> using namespace std; #define _ << " _ " << #define TRACE(x) cout << #x << " = " << x << endl #define fi first #define se second typedef pair<int, int> pii; const int MaxN = 1010, MaxR = 1e5 + 10; int n, r; vector<pii> e[MaxN]; bool con[MaxN][MaxN]; pii edg[MaxR]; bool vis[MaxR], stk[MaxR]; int pre[MaxR]; void dfs(int x, int y, int id) { vis[id] = true; stk[id] = true; for (pii z : e[y]) { if (!con[x][z.fi] && z.fi != x) { if (!vis[z.se]) { pre[z.se] = id; dfs(y, z.fi, z.se); } else if (stk[z.se]) { vector<int> cyc = {x}; for (int q = pre[id]; q != z.se; q = pre[q]) cyc.push_back(edg[q].fi + edg[q].se - cyc.back()); if (cyc.back() != y) cyc.push_back(y); int m = cyc.size(); for (int len = 3; len < m; len++) for (int i = 0; i < m; i++) { if (con[cyc[i]][cyc[(i + len) % m]]) { for (int j = (i + 1) % m; j != i; j = (j + 1) % m) cout << cyc[j] << " "; cout << cyc[i]; exit(0); } } } } } stk[id] = false; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> r; for (int i = 0; i < r; i++) { int x, y; cin >> x >> y; e[x].push_back({y, i}); e[y].push_back({x, i}); con[x][y] = con[y][x] = true; edg[i] = {x, y}; } for (int i = 1; i <= n; i++) sort(e[i].begin(), e[i].end()); for (int i = 0; i < r; i++) { if (!vis[i]) { dfs(edg[i].fi, edg[i].se, i); } } cout << "no"; return 0; }
#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...