oj.uz

Submission #244545

# Submission time Handle Problem Language Result Execution time Memory
244545 2020-07-04T09:28:14 Z cheeheng Potemkin cycle (CEOI15_indcyc) C++14
20 / 100
 183 ms 2472 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> AdjList[1005];
bool visited[1005];
bool AdjMat[1005][1005];
int dist[1005];
int p[1005];
bool forbidden[1005];

int main(){
    int N, R;
    scanf("%d%d", &N, &R);

    memset(AdjMat, 0, sizeof(AdjMat));
    for(int i = 0; i < R; i ++){
        int a, b;
        scanf("%d%d", &a, &b);
        a--;
        b--;

        AdjList[a].push_back(b);
        AdjList[b].push_back(a);
        AdjMat[a][b] = 1;
        AdjMat[b][a] = 1;
    }

    memset(visited, 0, sizeof(visited));

    for(int i = 0; i < N; i ++){
        queue<int> q;
        q.push(i);
        vector<int> component;
        component.push_back(i);
        memset(dist, -1, sizeof(dist));
        memset(p, -1, sizeof(p));
        dist[i] = 0;
        int x = -1;
        int y = -1;
        int minCycle = N+5;
        while(!q.empty()){
            int u = q.front(); q.pop();
            bool found = false;
            for(int v: AdjList[u]){
                if(dist[v] == -1){
                    component.push_back(v);
                    dist[v] = dist[u]+1;
                    p[v] = u;
                    q.push(v);
                }else if(v != p[u]){
                    int temp = dist[u]+dist[v] +1 ;
                    if(temp < minCycle){
                        minCycle = temp;
                        //printf("p[%d]=%d; p[%d]=%d\n", u, p[u], v, p[v]);
                        //found = true;
                        x = u;
                        y = v;
                    }
                }
            }
            if(found){break;}
        }

        if(minCycle <= N && minCycle >= 4){
            //printf("x=%d y=%d\n", x, y);
            vector<int> X;
            vector<int> Y;
            while(x != -1){
                X.push_back(x);
                x = p[x];
            }
            reverse(X.begin(), X.end());
            memset(forbidden, false, sizeof(forbidden));
            for(int x: X){
                forbidden[x] = true;
            }

            /*
            memset(dist, -1, sizeof(dist));
            memset(p, -1, sizeof(p));
            dist[i] = 0;
            while(!q.empty()){
                int u = q.front(); q.pop();
                for(int v: AdjList[u]){
                    if(dist[v] == -1 && !forbidden[v]){
                        component.push_back(v);
                        dist[v] = dist[u]+1;
                        p[v] = u;
                        q.push(v);
                    }
                }
            }
            */

            while(y != i){
                X.push_back(y);
                y = p[y];
            }

            for(int k: X){
                printf("%d ", k+1);
            }

            return 0;
        }
    }

    printf("no");
    return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &R);
     ~~~~~^~~~~~~~~~~~~~~~
indcyc.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1280 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 1408 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 12 ms 1408 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 183 ms 1920 KB Repeated vertex
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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