Submission #1257663

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

indcyc

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

int n, m;
vector<vector<int>> g;
vector<vector<char>> adjMat;
vector<int> path;
vector<char> used;
bool found = false;

bool is_induced_cycle(const vector<int> &cyc) {
    int L = (int)cyc.size();
    for (int i = 0; i < L; ++i) {
        for (int j = i + 1; j < L; ++j) {
            // skip consecutive pairs on the cycle (including last-first)
            if (j == i + 1) continue;
            if (i == 0 && j == L - 1) continue;
            if (adjMat[cyc[i]][cyc[j]]) return false; // chord found
        }
    }
    return true;
}

void dfs(int u, int start) {
    if (found) return;
    for (int v : g[u]) {
        if (found) return;
        if (v == start) {
            // path currently contains nodes from start ... u
            // check cycle length: path.size() (example accepts length 4)
            if ((int)path.size() >= 4) {
                if (is_induced_cycle(path)) {
                    // print and stop
                    for (int x : path) {
                        cout << x << " ";
                    }
                    cout << "\n";
                    found = true;
                    return;
                }
            }
        } else if (!used[v]) {
            used[v] = 1;
            path.push_back(v);
            dfs(v, start);
            path.pop_back();
            used[v] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m)) return 0;
    g.assign(n+1, {});
    adjMat.assign(n+1, vector<char>(n+1, 0));
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        if (!adjMat[u][v]) {
            g[u].push_back(v);
            g[v].push_back(u);
            adjMat[u][v] = adjMat[v][u] = 1;
        }
    }
    used.assign(n+1, 0);

    for (int s = 1; s <= n && !found; ++s) {
        // start DFS from s
        used[s] = 1;
        path.clear();
        path.push_back(s);
        dfs(s, s);
        path.pop_back();
        used[s] = 0;
    }

    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