Submission #1231348

#TimeUsernameProblemLanguageResultExecution timeMemory
1231348kaiboyPotemkin cycle (CEOI15_indcyc)C++20
20 / 100
8 ms2120 KiB
// coached by rainboy #include <algorithm> #include <iostream> #include <vector> using namespace std; const int N = 1000; vector<int> ej[N]; bool aa[N][N], visited[N], inqu[N]; int dd[N], pp[N], qu[N], cnt; void dfs(int i, int i_) { if (i == i_) return; if (aa[i][i_]) { if (!inqu[i]) qu[cnt++] = i; return; } if (visited[i]) return; visited[i] = true; for (int j : ej[i]) dfs(j, i_); } int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); int n, m; cin >> n >> m; while (m--) { int i, j; cin >> i >> j, i--, j--; ej[i].push_back(j); ej[j].push_back(i); aa[i][j] = aa[j][i] = true; } for (int i_ = 0; i_ < n; i_++) { for (int i = 0; i < n; i++) visited[i] = false; visited[i_] = true; for (int i = 0; i < n; i++) if (!aa[i][i_] && !visited[i]) { cnt = 0, dfs(i, i_); for (int g = 0; g < cnt; g++) { int s = qu[g]; inqu[s] = false; for (int h = g + 1; h < cnt; h++) { int t = qu[h]; if (!aa[s][t]) { for (int i = 0; i < n; i++) dd[i] = n; int cnt = 0; dd[s] = 0, pp[s] = -1, qu[cnt++] = s; for (int h = 0; h < cnt; h++) { int i = qu[h], d = dd[i] + 1; for (int j : ej[i]) if (j != i_ && (j == t || !aa[j][i_]) && dd[j] == n) dd[j] = d, pp[j] = i, qu[cnt++] = j; } cout << s + 1 << ' ' << i_ + 1; for (int i = t; i != s; i = pp[i]) cout << ' ' << 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...