Submission #1059314

#TimeUsernameProblemLanguageResultExecution timeMemory
1059314MilosMilutinovicPotemkin cycle (CEOI15_indcyc)C++14
10 / 100
1085 ms119636 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1000; bool c[N][N]; vector<int> g[N]; bitset<N> bs[N][N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; 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 k = 0; k < n; k++) { vector<bool> del(n); del[k] = true; for (int i : g[k]) { del[i] = true; } vector<int> p(n); iota(p.begin(), p.end(), 0); vector<int> sz(n, 1); function<int(int)> Root = [&](int x) { return p[x] == x ? x : p[x] = Root(p[x]); }; auto Merge = [&](int x, int y) { x = Root(x); y = Root(y); if (x == y) { return; } if (sz[x] < sz[y]) { swap(x, y); } sz[x] += sz[y]; p[y] = x; }; for (int i = 0; i < n; i++) { if (del[i]) { continue; } for (int j : g[i]) { if (del[j]) { continue; } Merge(i, j); } } for (int i = 0; i < n; i++) { if (!del[i]) { continue; } for (int j : g[i]) { if (del[j]) { continue; } bs[k][i][Root(j)] = 1; } } } for (int i = 0; i < n; i++) { for (int j : g[i]) { if (i > j) { continue; } for (int k : g[g[i].size() < g[j].size() ? i : j]) { if (i == k || j == k || !c[i][k] || !c[j][k]) { continue; } if ((bs[k][i] & bs[k][j]).count() == 0) { 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) { assert(false); 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...