oj.uz

Submission #54783

# Submission time Handle Problem Language Result Execution time Memory
54783 2018-07-05T05:20:03 Z 노영훈(#1508) Potemkin cycle (CEOI15_indcyc) C++11
30 / 100
 1000 ms 2836 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];

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);
    }


    bool A[VMX]={}, B[VMX]={};

    for(int i=1; i<=m; i++){
        int u=E[i].u, v=E[i].v;
        for(int x:G[u]) A[x]=true;
        for(int x:G[v]) B[x]=true;

        for(int x:G[u]){
            if((A[x]&&B[x]) || x==u || x==v) continue;
            for(int y:G[x]){
                // cout<<v<<' '<<u<<' '<<x<<' '<<y<<'\n';
                if(!A[y] && B[y] && y!=u && y!=v){
                    found(u,x,y,v);
                }
            }
        }
        for(int x:G[v]){
            if((A[x]&&B[x]) || x==u || x==v) continue;
            for(int y:G[x]){
                // cout<<u<<' '<<v<<' '<<x<<' '<<y<<'\n';
                if(A[y] && !B[y] && y!=u && y!=v){
                    found(v,x,y,u);
                }
            }
        }

        for(int x:G[u]) A[x]=false;
        for(int x:G[v]) B[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 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 2 ms 552 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 568 KB Expected integer, but "no" found

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 780 KB Output is correct
2 Incorrect 6 ms 784 KB Expected integer, but "no" found
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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