oj.uz

Submission #54973

# Submission time Handle Problem Language Result Execution time Memory
54973 2018-07-05T15:27:12 Z Diuven Potemkin cycle (CEOI15_indcyc) C++11
30 / 100
 1000 ms 7140 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 6 ms 5256 KB Output is correct
3 Correct 6 ms 5256 KB Output is correct
4 Correct 6 ms 5256 KB Output is correct
5 Correct 6 ms 5256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5256 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5308 KB Output is correct
2 Incorrect 7 ms 5328 KB Wrong answer on graph without induced cycle

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5328 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5456 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 5556 KB Output is correct
2 Correct 7 ms 5556 KB Output is correct
3 Incorrect 8 ms 5612 KB Wrong adjacency
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 5612 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 409 ms 6892 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 6892 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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