Submission #1059298

#TimeUsernameProblemLanguageResultExecution timeMemory
1059298MilosMilutinovicPotemkin cycle (CEOI15_indcyc)C++14
70 / 100
1055 ms2140 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<vector<bool>> c(n, vector<bool>(n)); vector<vector<int>> g(n); for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; --x; --y; c[x][y] = true; c[y][x] = true; g[x].push_back(y); g[y].push_back(x); } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (c[i][j]) { continue; } for (int k = 0; k < n; k++) { if (i == k || j == k || !c[i][k] || !c[j][k]) { continue; } vector<bool> del(n); del[k] = true; for (int p : g[k]) { if (p != i && p != j) { del[p] = true; } } vector<int> p(n, -1); vector<int> que(1, i); vector<int> d(n, -1); d[i] = 0; for (int b = 0; b < (int) que.size(); b++) { int i = que[b]; for (int j : g[i]) { if (del[j]) { continue; } if (d[j] == -1) { p[j] = i; d[j] = d[i] + 1; que.push_back(j); } } } if (p[j] == -1) { continue; } vector<int> seq; for (int v = j; v != -1; v = p[v]) { seq.push_back(v); } seq.push_back(k); for (int i = 0; i < (int) seq.size(); i++) { cout << seq[i] + 1 << " "; } cout << '\n'; return 0; } } } cout << "no" << '\n'; 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...