oj.uz

Submission #405327

# Submission time Handle Problem Language Result Execution time Memory
405327 2021-05-16T08:57:25 Z MeGustaElArroz23 Potemkin cycle (CEOI15_indcyc) C++14
20 / 100
 1000 ms 2844 KB 
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;

int main(){
    int n,m;
    cin >> n >> m;
    vvi conexiones(n);
    for (int i=0;i<m;i++){
        int a,b;
        cin >> a >>b;
        a--;
        b--;
        conexiones[a].push_back(b);
        conexiones[b].push_back(a);
    }
    for (int i=0;i<n;i++){
        for (int x:conexiones[i]){
            if (x<i) continue;
            vector<bool> porvisitar(n,true);
            porvisitar[i]=false;
            queue<int> cola;
            for (int y:conexiones[i]){
                if (y!=x) cola.push(y);
            }
            while (cola.size()){
                int y=cola.front();
                cola.pop();
                if (porvisitar[y]){
                    porvisitar[y]=false;
                    for (int z:conexiones[y]) cola.push(z);
                }
            }
            if (porvisitar[x]) cout << i+1 << ' '<<x+1<<'\n';
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Too short sequence
2 Incorrect 1 ms 204 KB Wrong answer on graph without induced cycle
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Too short sequence

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Too short sequence
2 Incorrect 1 ms 204 KB Unexpected end of file - token expected

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Too short sequence

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 204 KB Too short sequence
2 Incorrect 13 ms 300 KB Unexpected end of file - token expected

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 360 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 Correct 120 ms 332 KB Too short sequence
2 Incorrect 120 ms 332 KB Unexpected end of file - token expected

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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