Submission #1257659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257659		anha3k25cvp	Potemkin cycle (CEOI15_indcyc)	C++20	30 / 100	1096 ms	1348 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<int>> adj;
vector<bool> visited;
vector<int> path;
bool found = false;

// Kiểm tra chu trình không có dây tắt
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;
}

void dfs(int u, int start) {
    if (found) return;
    for (int v : adj[u]) {
        if (v == start && path.size() >= 4) {
            if (check_no_chord(path)) {
                for (int i = 0; i < (int)path.size(); i++) {
                    if (i) cout << " ";
                    cout << path[i];
                }
                cout << "\n";
                found = true;
            }
            return;
        }
        if (!visited[v]) {
            visited[v] = true;
            path.push_back(v);
            dfs(v, start);
            path.pop_back();
            visited[v] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    adj.assign(n+1, {});
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    visited.assign(n+1, false);
    for (int s = 1; s <= n && !found; s++) {
        visited[s] = true;
        path = {s};
        dfs(s, s);
        visited[s] = false;
    }

    if (!found) cout << "no\n";
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 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