Submission #851954

#	Time	Username	Problem	Language	Result	Execution time	Memory
851954		Nhoksocqt1	Potemkin cycle (CEOI15_indcyc)	C++17	100 / 100	151 ms	10416 KiB

indcyc

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

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 1003;

vector<int> adj[MAXN];
int used[MAXN][MAXN], tr[MAXN][MAXN];
int numNode, numEdge;
bool adjc[MAXN][MAXN];

void getPath(const vector<int> &nodes) {
    int l(0), r(sz(nodes) - 1);
    for (int i = 0; i < sz(nodes); ++i) {
        for (int j = i + 3; j < sz(nodes); ++j) {
            if(adjc[nodes[i]][nodes[j]]) {
                l = i, r = j;
                break;
            }
        }
    }

    for (int it = l; it <= r; ++it)
        cout << nodes[it] << ' ';

    exit(0);
}

void dfs(int x, int y, int p) {
    used[x][y] = 1;
    tr[x][y] = p;
    for (int it = 0; it < sz(adj[y]); ++it) {
        int c(adj[y][it]);
        if(adjc[c][x])
            continue;

        if(used[y][c] == 1) {
            vector<int> node;
            while(x != c) {
                node.push_back(y);
                int tmp = tr[x][y];
                y = x;
                x = tmp;
            }

            node.push_back(y);
            node.push_back(x);
            getPath(node);
        } else
            if(!used[y][c]) {
                dfs(y, c, x);
            }
    }

    used[x][y] = 2;
}

void process() {
    cin >> numNode >> numEdge;
    for (int i = 0; i < numEdge; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        adjc[u][v] = adjc[v][u] = 1;
    }

    for (int i = 1; i <= numNode; ++i)
        adjc[i][i] = 1;

    for (int x = 1; x <= numNode; ++x) {
        for (int y = 1; y <= numNode; ++y) {
            if(adjc[x][y] && !used[x][y])
                dfs(x, y, -1);
        }
    }

    cout << "no\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    process();
    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: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10