Submission #244568

#	Time	Username	Problem	Language	Result	Execution time	Memory
244568		cheeheng	Potemkin cycle (CEOI15_indcyc)	C++14	30 / 100	1098 ms	2304 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 N, R;
vector<int> stack1;
bool picked[1005];

void dfs(int u, int s, int k){
    /*printf("dfs(%d, %d, %d): ", u, s, k);
    for(int x: stack1){
        printf("%d ", x);
    }
    printf("\n");*/
    if(k > N){return;}
    if(u == s && k > 0){
        if(k < 4){return;}
        bool boleh = true;
        for(int i = 0; i < (int)stack1.size()-1; i ++){
            for(int j = i+2; j < (int)stack1.size()-1; j ++){
                if(min(j-i, (int)stack1.size()-1-(j-i)) < 2){continue;}
                int x = stack1[i];
                int y = stack1[j];
                if(AdjMat[x][y]){
                    //printf("%d and %d connected\n", x, y);
                    boleh = false;
                    break;
                }
            }
            if(!boleh){break;}
        }
        if(boleh){
            stack1.pop_back();
            for(int i: stack1){
                printf("%d ", i);
            }
            exit(0);
        }
    }else{
        for(int v = 1; v <= N; v ++){
            if(AdjMat[u][v] && u != v && !picked[v]){
                picked[v] = true;
                stack1.push_back(v);
                dfs(v, s, k+1);
                stack1.pop_back();
                picked[v] = false;
            }
        }
    }
}

int main(){
    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;
    }

    if(N <= 1000){
        for(int i = 1; i <= N; i ++){
            stack1.clear();
            stack1.push_back(i);
            memset(picked, false, sizeof(picked));
            dfs(i, i, 0);
        }
        printf("no");
        return 0;
    }

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

    for(int i = 1; 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:59: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:64: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: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 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