Submission #244445

#	Time	Username	Problem	Language	Result	Execution time	Memory
244445		cheeheng	Potemkin cycle (CEOI15_indcyc)	C++14	20 / 100	186 ms	2356 KiB

indcyc

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

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

            return 0;
        }
    }

    printf("no");
    return 0;
}

Compilation message (stderr)

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 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10