답안 #598874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
598874	2022-07-19T06:45:43 Z	박상훈(#8456)	Potemkin cycle (CEOI15_indcyc)	C++17	60 / 100	1000 ms	6812 KB

indcyc

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<int> adj[1010];
int n, no[1010][1010], pa[1010], subtree[1010];
bool visited[1010];

void getans(int R, int s, int e){
    //printf("%d %d %d: ", R, s, e);

    vector<int> ans1, ans2;
    for (;s!=R;s=pa[s]) ans1.push_back(s);
    for (;e!=R;e=pa[e]) ans2.push_back(e);
    reverse(ans2.begin(), ans2.end());

    for (auto &x:ans1) printf("%d ", x);
    printf("%d ", R);
    for (auto &x:ans2) printf("%d ", x);
    exit(0);
}

void bfs(int s){
    fill(pa+1, pa+n+1, 0);
    fill(subtree+1, subtree+n+1, 0);
    fill(visited+1, visited+n+1, 0);

    queue<int> q;
    vector<pair<int, int>> X;
    visited[s] = 1;

    for (auto &v:adj[s]){
        visited[v] = 1;
        pa[v] = s;
        subtree[v] = v;
        q.push(v);
    }

    while(!q.empty()){
        int cur = q.front(); q.pop();
        for (auto &nxt:adj[cur]) if (nxt!=s){
            if (visited[nxt]){
                if (subtree[cur]==subtree[nxt]) continue;
                if (pa[cur]==s && pa[nxt]==s){
                    no[cur][nxt] = 1;
                    no[nxt][cur] = 1;
                    X.emplace_back(cur, nxt);
                }
                else if (no[subtree[cur]][subtree[nxt]]) continue;
                else{
                    getans(s, cur, nxt);
                }
            }
            else{
                visited[nxt] = 1;
                q.push(nxt);
                pa[nxt] = cur;
                subtree[nxt] = subtree[cur];
            }
        }
    }

    for (auto &[x, y]:X) no[x][y] = no[y][x] = 0;
}

int main(){
    int m;
    scanf("%d %d", &n, &m);
    for (int i=1;i<=m;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    for (int i=1;i<=n;i++){
        bfs(i);
    }

    assert(m!=n*2-2);
    printf("no\n");
    return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
indcyc.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	340 KB	Output is correct
5	Correct	212 KB	Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	724 KB	Expected integer, but "no" found
2	Halted	0 ms	0 KB	-

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	1580 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	2 ms	724 KB	Output is correct
4	Correct	18 ms	1552 KB	Output is correct

Subtask #7
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	14 ms	1744 KB	Expected integer, but "no" found
2	Halted	0 ms	0 KB	-

Subtask #8
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	3764 KB	Output is correct
2	Correct	7 ms	2900 KB	Output is correct
3	Correct	471 ms	4952 KB	Output is correct
4	Correct	177 ms	4620 KB	Output is correct

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	218 ms	4972 KB	Expected integer, but "no" found
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

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