Submission #54983

#	Time	Username	Problem	Language	Result	Execution time	Memory
54983		Diuven	Potemkin cycle (CEOI15_indcyc)	C++11	70 / 100	1084 ms	2420 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=1010, inf=2e9;

int n, m;
vector<int> G0[MX], G1[MX];
vector<pii> E;

bool adj[MX];

void found(int a, int b, int c){
    // cout<<a<<' '<<b<<' '<<c<<'\n';
    queue<int> ans, Q;
    int prv[MX];
    for(int i=1; i<=n; i++) prv[i]=-1;
    prv[a]=b; Q.push(a);
    while(!Q.empty()){
        int v=Q.front(); Q.pop();
        for(int x:G1[v]){
            if(prv[x]>=0) continue;
            prv[x]=v;
            Q.push(x);
        }
    }
    int v=c;
    while(v>0){
        ans.push(v); v=prv[v];
    }
    while(!ans.empty()) cout<<ans.front()<<' ', ans.pop();
    cout<<'\n';
    exit(0);
}

void search(int st, int out){
    bool ign[MX]={}; ign[out]=true;
    for(int i=1; i<=n; i++) G1[i].clear();
    for(int x:G0[st]) if(adj[x]) ign[x]=true;

    for(pii &e:E){
        int u,v; tie(u,v)=e;
        if(ign[u] || ign[v]) continue;
        G1[u].push_back(v);
        G1[v].push_back(u);
    }

    int D[MX];
    fill(D+1, D+n+1, -1);
    D[st]=0;
    queue<int> Q;
    Q.push(st);
    while(!Q.empty()){
        int v=Q.front(); Q.pop();
        for(int x:G1[v]){
            if(D[x]>=0) continue;
            D[x]=D[v]+1;
            Q.push(x);
        }
    }
    int pt=-1;
    for(int i=1; i<=n; i++){
        if(i==st || !adj[i] || ign[i] || D[i]<0) continue;
        if(pt<0 || D[pt]>D[i]) pt=i;
    }
    if(pt>0) found(st,out,pt);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        int u, v; cin>>u>>v;
        G0[u].push_back(v);
        G0[v].push_back(u);
        E.push_back({u,v});
    }
    for(int v=1; v<=n; v++){
        for(int x:G0[v]) adj[x]=true;
        for(int x:G0[v]) search(x, v);
        for(int x:G0[v]) adj[x]=false;
    }
    cout<<"no\n";
    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