Submission #1245327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245327		pasta	Potemkin cycle (CEOI15_indcyc)	C++20	70 / 100	1095 ms	5700 KiB

indcyc

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>

using namespace std;

const int N = 1 + 1e3;
const int inf = 7 + 1e9;

struct Edge {
    int u, v;
};

int node = 0, ncc = 0;
vector <Edge> e;
vector <int> num, low, a;
vector <vector <int>> adj;
stack <int> q;

void dfs(int u, int p) {
    num[u] = low[u] = ++ node;
    q.push(u);
    for (int i : adj[u]) {
        int v = e[i].u + e[i].v - u;
        if (v == p)
            continue;
        if (!num[v]) {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
        }
        else
            low[u] = min(low[u], num[v]);
    }
    if (num[u] == low[u]) {
        int v = 0;
        ncc ++;
        while (v != u) {
            v = q.top(); q.pop();
            a[v] = ncc;
        }
    }
}

int main() {
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
   
    int n, m; 
    cin >> n >> m;
    e.resize(m + 1);
    adj.resize(n + 1);
    for (int i = 1; i <= m; i ++) {
        cin >> e[i].u >> e[i].v;
        adj[e[i].u].push_back(i);
        adj[e[i].v].push_back(i);
    }
    num.assign(n + 1, 0);
    low.assign(n + 1, 0);
    a.assign(n + 1, 0);
    for (int i = 1; i <= n; i ++)
        if (!num[i])
            dfs(i, 0);
    vector <vector <int>> f(n + 1, vector <int> (n + 1, 0));
    for (int i = 1; i <= m; i ++) {
        int u = e[i].u, v = e[i].v;
        if (a[u] == a[v])
            f[u][v] = f[v][u] = 1;
    }
    queue <int> q;
    for (int id = 1; id <= m; id ++) {
        int s = e[id].u, t = e[id].v;
        if (a[s] != a[t])
            continue;
        vector <int> ok(n + 1, 0), tr(n + 1, -1);
        for (int u = 1; u <= n; u ++)
            if (a[u] == a[s] && !(f[s][u] & f[t][u]))
                ok[u] = 1;
        ok[t] = 1;
        q.push(s);
        tr[s] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i : adj[u]) {
                int v = e[i].u + e[i].v - u;
                if (u == s && v == t)
                    continue;
                if (!ok[v] || tr[v] >= 0)
                    continue;
                q.push(v);
                tr[v] = u;
            }
        }
        if (tr[t] >= 0) {
            int u = t;
            while (u != 0) {
                cout << u << ' ';
                u = tr[u];
            }
            return 0;
        }
    }
    cout << "no";
    return 0;
}

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