제출 #1081671

#제출 시각아이디문제언어결과실행 시간메모리
108167142kangarooPotemkin cycle (CEOI15_indcyc)C++17
20 / 100
40 ms10076 KiB
// // Created by 42kangaroo on 30/08/2024. // #include "bits/stdc++.h" using namespace std; using g_t = vector<set<int>>; void dfs(int n, int p, int d, g_t& g, vector<pair<int,int>>& st, vector<int>& de) { de[n] = d; vector<int> up; st.push_back({n, de[n] + 1}); for (auto e: g[n]) { if (e == p || de[e] > de[n]) continue; if (de[e] != -1) { st[de[e]].second++; up.push_back(de[e]); } else dfs(e, n, d + 1, g, st, de); } std::sort(up.begin(), up.end()); int i = de[n] - 2; for (; i >= 0; --i) { if (up.empty() || up.back() != i) break; up.pop_back(); } i--; for (auto e: g[n]) { if (e == p || de[e] > de[n]) continue; if (de[e] != -1) { if (i > de[e] || st[de[e]].second < de[n]) { int j = de[n] - 1; for (; j > de[e]; --j) { if (g[st[j].first].find(n) == g[st[j].first].end() || g[st[j].first].find(e) == g[st[j].first].end()) break; } assert(j > de[e]); int act = n; while (act != st[j].first) { cout << act + 1 << " "; int be = act; for (auto f: g[act]) { if (de[f] < de[be] && de[f] >= de[st[j].first]) { be = f; } } act = be; } act = st[j].first; while (act != e) { cout << act + 1 << " "; int be = act; for (auto f: g[act]) { if (de[f] < de[be] && de[f] >= de[e] ) { be = f; } } act = be; } cout << e + 1; exit(0); } } } for (auto e: g[n]) { if (e == p || de[e] > de[n]) continue; if (de[e] != -1) { st[de[e]].second--; } } st.pop_back(); } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; g_t g(n); for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; g[--a].insert(--b); g[b].insert(a); } vector<int> de(n, -1); vector<pair<int,int>> st; for (int i = 0; i < n; ++i) { if (de[i] == -1) { dfs(i, i, 0, g, st, de); } } cout << "no"; }
#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...