oj.uz

답안 #244568

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244568 2020-07-04T09:53:34 Z cheeheng Potemkin cycle (CEOI15_indcyc) C++14
30 / 100
 1000 ms 2304 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 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

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.0 / 10.0

# 결과 실행 시간 메모리 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 1408 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1280 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1280 KB Output is correct
2 Correct 6 ms 1280 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1085 ms 1280 KB Time limit exceeded

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1091 ms 1408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1092 ms 1408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1087 ms 1408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1098 ms 1920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1091 ms 1664 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1088 ms 2304 KB Time limit exceeded
2 Halted 0 ms 0 KB -