제출 #54973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54973		Diuven	Potemkin cycle (CEOI15_indcyc)	C++11	30 / 100	1073 ms	7140 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, 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 chk[MX]={};
    for(int i=1; i<=n; i++) chk[i]=adj[i], G1[i].clear();
    chk[st]=chk[out]=false;
    for(pii &e:E){
        int u,v; tie(u,v)=e;
        if(u==out || v==out) continue;
        if(adj[u] && adj[v]){
            if(u!=st) swap(u,v);
            if(u==st) chk[v]=false;
            continue;
        }
        G1[u].push_back(v);
        G1[v].push_back(u);
    }

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

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: 0 / 10
• Subtask 4: 10 / 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