oj.uz

Submission #54983

# Submission time Handle Problem Language Result Execution time Memory
54983 2018-07-05T16:10:15 Z Diuven Potemkin cycle (CEOI15_indcyc) C++11
70 / 100
 1000 ms 2420 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 560 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 560 KB Output is correct
2 Correct 2 ms 560 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 KB Output is correct
2 Correct 20 ms 716 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 876 KB Output is correct
2 Correct 4 ms 876 KB Output is correct
3 Correct 12 ms 940 KB Output is correct
4 Correct 401 ms 940 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 940 KB Output is correct
2 Correct 151 ms 940 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 2136 KB Output is correct
2 Correct 119 ms 2136 KB Output is correct
3 Execution timed out 1056 ms 2136 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 2136 KB Output is correct
2 Execution timed out 1084 ms 2136 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 2420 KB Time limit exceeded
2 Halted 0 ms 0 KB -