제출 #1078997

#제출 시각아이디문제언어결과실행 시간메모리
1078997jk_Potemkin cycle (CEOI15_indcyc)C++14
100 / 100
191 ms6740 KiB
#include <bits/stdc++.h> using namespace std; int main() { int n, r; cin >> n >> r; if (n <= 3) { cout << "no\n"; return 0; } vector<vector<int>> g(n); vector<vector<bool>> m(n, vector<bool>(n)); for (int i = 0; i < n; ++i) m[i][i] = true; for (int i = 0; i < r; ++i) { int a, b; cin >> a >> b; --a; --b; g[a].push_back(b); g[b].push_back(a); m[a][b] = true; m[b][a] = true; } auto complete_path = [&](int a, int mid, int c) -> vector<int> { assert(!m[a][c]); vector<int> prev(n, -1); queue<int> q; prev[a] = mid; q.push(a); while (!q.empty()) { int v = q.front(); q.pop(); for (auto w : g[v]) { if (prev[w] != -1) continue; prev[w] = v; if (w == c) { vector<int> path; while (w != mid) { path.push_back(w); w = prev[w]; } path.push_back(mid); return path; } if (m[w][mid]) continue; q.push(w); } } assert(false); return {}; }; auto solve = [&](auto&& self, int root, vector<int> vertices, vector<int> clique) -> vector<int> { assert(is_sorted(vertices.begin(), vertices.end())); assert(is_sorted(clique.begin(), clique.end())); auto is_active = [&](int v) { return binary_search(vertices.begin(), vertices.end(), v); }; auto is_clique = [&](int v) { return binary_search(clique.begin(), clique.end(), v); }; // cerr << "solving with root="<<root<<" with clique=["; // for(auto x : clique) cerr << " " << x; // cerr<< "] on V="; // for(auto x : vertices) cerr << " " << x; // cerr << '\n'; vector<int> group(n, -1); group[root] = 0; for (auto x : g[root]) { if (is_active(x)) { assert(!is_clique(x)); group[x] = 0; } } for (auto x : clique) { assert(!is_active(x)); group[x] = 0; } int idx=1; vector<int> members; vector<int> adjacent; auto dfs = [&](auto&& self, int v) -> void { if (group[v] != -1 || !is_active(v)) return; group[v] = idx; members.push_back(v); for (auto w : g[v]) { if (group[w] == 0) adjacent.push_back(w); else self(self, w); } }; for (int i : vertices) { // cerr <<"v="<<i<<" group="<<group[i]<<'\n'; if (group[i] == -1) { members.clear(); adjacent.clear(); idx++; dfs(dfs, i); sort(adjacent.begin(), adjacent.end()); adjacent.erase(unique(adjacent.begin(), adjacent.end()), adjacent.end()); assert(!binary_search(adjacent.begin(), adjacent.end(), root)); sort(members.begin(), members.end()); // cerr << "group "; // for(auto x : members) cerr << " " << x; // cerr << " adjacent cliques "; // for(auto x : adjacent) cerr << " " << x; // cerr << '\n'; for (size_t i = 0; i < adjacent.size(); ++i) { for (size_t j = i+1; j < adjacent.size(); ++j) { if (!m[adjacent[i]][adjacent[j]]) { return complete_path(adjacent[i], root, adjacent[j]); } } } int new_root; if (!adjacent.empty()) { new_root = adjacent.back(); adjacent.pop_back(); } else if (!members.empty()) { new_root = members.back(); members.pop_back(); } else { continue; } auto ans = self(self, new_root, members, adjacent); if (!ans.empty()) return ans; } } vector<int> g0 = g[root]; sort(g0.begin(), g0.end()); vector<int> new_vertices; set_intersection(g0.begin(), g0.end(), vertices.begin(), vertices.end(), back_inserter(new_vertices)); if (!new_vertices.empty()) { int new_root; if (clique.empty()) { new_root = new_vertices.back(); new_vertices.pop_back(); } else { new_root = clique.back(); clique.pop_back(); } // cerr << "self recurse with root="<<new_root<<" adjacent="; // for(auto x : new_vertices) cerr << " " << x; // cerr << "\n"; return self(self, new_root, new_vertices, clique); } return {}; }; vector<int> all_vertices_except_0(n-1); iota(all_vertices_except_0.begin(), all_vertices_except_0.end(), 1); auto ans = solve(solve, 0, all_vertices_except_0, {}); if (!ans.empty()) { cout << ans[0]+1; for (int i = 1; i < (int)ans.size(); ++i) { cout << " " << ans[i]+1; assert(m[ans[i-1]][ans[i]]); for (int j = i+2; j < i+(int)ans.size()-2; ++j) { assert(!m[ans[i]][ans[j%ans.size()]]); } } cout << '\n'; } else { cout << "no\n"; } }
#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...