oj.uz

Submission #54778

# Submission time Handle Problem Language Result Execution time Memory
54778 2018-07-05T05:09:53 Z 노영훈(#1508) Potemkin cycle (CEOI15_indcyc) C++11
0 / 100
 71 ms 3108 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int EMX=100010, inf=2e9, VMX=1010;

int n, m;
vector<int> G[VMX];
struct edge {
    int u, v, idx;
} E[EMX];

bool adj[VMX][VMX];

void found(int a, int b, int c, int d){
    cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n';
    exit(0);
}

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;
        E[i]={u,v,i};
        G[u].push_back(v);
        G[v].push_back(u);
        adj[u][v]=adj[v][u]=true;
    }


    int cnt[VMX]={};

    for(int i=1; i<=m; i++){
        int u=E[i].u, v=E[i].v;
        for(int x:G[u]) cnt[x]++;
        for(int x:G[v]) cnt[x]++;
        for(int x:G[u]){
            if(cnt[x]==2 || x==v) continue;
            for(int y:G[x]){
                if(cnt[y]==0){
                    found(v,u,x,y);
                }
            }
        }
        for(int x:G[v]){
            if(cnt[x]==2 || x==u) continue;
            for(int y:G[x]){
                if(cnt[y]==0){
                    found(u,v,x,y);
                }
            }
        }
        for(int x:G[u]) cnt[x]--;
        for(int x:G[v]) cnt[x]--;
    }
    cout<<"no\n";

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 488 KB Wrong adjacency

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 704 KB Wrong adjacency

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 936 KB Wrong answer on graph without induced cycle
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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