Submission #1257661

#TimeUsernameProblemLanguageResultExecution timeMemory
1257661anha3k25cvpPotemkin cycle (CEOI15_indcyc)C++20
0 / 100
164 ms1504 KiB
#include <bits/stdc++.h> using namespace std; int n, m; vector<vector<int>> adj; vector<vector<bool>> hasEdge; vector<int> bfs_find_path(int start, int end, int ban_u, int ban_v) { vector<int> par(n+1, -1); queue<int> q; vector<bool> vis(n+1, false); q.push(start); vis[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if ((u == ban_u && v == ban_v) || (u == ban_v && v == ban_u)) continue; // bỏ cạnh bị cấm if (!vis[v]) { vis[v] = true; par[v] = u; q.push(v); if (v == end) { // reconstruct path vector<int> path; int cur = v; while (cur != -1) { path.push_back(cur); cur = par[cur]; } reverse(path.begin(), path.end()); return path; } } } } return {}; } bool check_no_chord(const vector<int>& cycle) { int k = cycle.size(); unordered_map<int,int> pos; for (int i = 0; i < k; i++) pos[cycle[i]] = i; for (int i = 0; i < k; i++) { for (int v : adj[cycle[i]]) { if (pos.count(v)) { int j = pos[v]; int dist = abs(i - j); dist = min(dist, k - dist); if (dist > 1) return false; // có dây tắt } } } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; adj.assign(n+1, {}); hasEdge.assign(n+1, vector<bool>(n+1, false)); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); hasEdge[u][v] = hasEdge[v][u] = true; } bool found = false; for (int u = 1; u <= n && !found; u++) { for (int v : adj[u]) { if (u < v) { // xét mỗi cạnh một lần auto path = bfs_find_path(u, v, u, v); if (!path.empty() && (int)path.size() >= 4) { // ghép lại thành chu trình path.push_back(u); if (check_no_chord(path)) { for (int i = 0; i < (int)path.size()-1; i++) { if (i) cout << " "; cout << path[i]; } cout << "\n"; found = true; break; } } } } } if (!found) 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...