oj.uz

Submission #598874

# Submission time Handle Problem Language Result Execution time Memory
598874 2022-07-19T06:45:43 Z 박상훈(#8456) Potemkin cycle (CEOI15_indcyc) C++17
60 / 100
 1000 ms 6812 KB 
#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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory 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

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 6812 KB Time limit exceeded
2 Halted 0 ms 0 KB -