Submission #110017

#	Time	Username	Problem	Language	Result	Execution time	Memory
110017		someone_aa	Potemkin cycle (CEOI15_indcyc)	C++17	60 / 100	545 ms	2168 KiB

indcyc

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 1010;

bool edge[maxn][maxn];
vector<int>g[maxn];
int n, m;

class dsu {
public:
    int n, uparent[maxn], usize[maxn];

    void init(int _n) {
        n = _n;
        for(int i=0;i<=n;i++) {
            usize[i] = 1;
            uparent[i] = i;
        }
    }
    int root(int x) {
        while(x != uparent[x]) {
            x = uparent[x];
        }
        return x;
    }
    bool connected(int u, int v) {
        return root(u) == root(v);
    }
    void unite(int u, int v) {
        u = root(u);
        v = root(v);

        if(u == v) return;
        if(usize[u] > usize[v]) {
            uparent[v] = u;
            usize[u] += usize[v];
        }
        else {
            uparent[u] = v;
            usize[v] += usize[u];
        }
    }
};

dsu x;
bool visited[maxn];
int root;

bool f_edge[maxn];
int parent[maxn];

bool find_path(int root, int i, int j) {
    memset(visited,false,sizeof(visited));
    memset(parent,-1,sizeof(parent));

    parent[i] = root;
    parent[root] = 0;

    visited[root] = true;
    visited[i] = true;
    queue<int>q;
    q.push(i);

    while(!q.empty()) {
        int curr = q.front();
        q.pop();

        for(int i:g[curr]) {
            if(!visited[i] && (!f_edge[i] || i == j)) {
                visited[i] = true;
                parent[i] = curr;
                q.push(i);
            }
        }
    }

    if(!visited[j]) return false;

    int x = j;
    while(x) {
        cout<<x<<" ";
        x = parent[x];
    } cout<<"\n";
    return true;
}

void dfs(int node) {
    if(visited[node] || f_edge[node]) return;
    visited[node] = true;

    for(int i:g[node]) {
        if(!visited[i]) {
            dfs(i);
            x.unite(i, node);
        }
    }
}

void solve() {
    bool found = false;
    for(root=1;root<=n;root++) {
        memset(f_edge, false,sizeof(f_edge));
        memset(visited,false,sizeof(visited));
        x.init(n);

        visited[root] = true;
        for(int i:g[root]) {
            f_edge[i] = true;
        }

        for(int i=1;i<=n;i++) {
            if(!visited[i]) {
                dfs(i);
            }
        }

        for(int i:g[root]) {
            for(int j:g[root]) {
                if(i < j && !edge[i][j] && x.connected(i, j)) {
                    found = find_path(root, i, j);
                }
            }
            if(found) break;
        }
        if(found) break;
    }
    if(!found) {
        cout<<"no\n";
    }
}

int main() {
    cin>>n>>m;
    int u, v;
    for(int i=0;i<m;i++) {
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
        edge[u][v] = edge[v][u] = true;
    }
    solve();
    return 0;
}

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