Submission #1257665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257665		anha3k25cvp	Potemkin cycle (CEOI15_indcyc)	C++20	0 / 100	166 ms	1504 KiB

indcyc

#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;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10