oj.uz

Submission #598892

# Submission time Handle Problem Language Result Execution time Memory
598892 2022-07-19T07:17:34 Z 박상훈(#8456) The Forest of Fangorn (CEOI14_fangorn) C++17
0 / 100
 89 ms 65536 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);
    }

    printf("no\n");
    return 0;
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.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);
      |     ~~~~~^~~~~~~~~~~~~~~~~
fangorn.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
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Runtime error 84 ms 65536 KB Execution killed with signal 9
5 Runtime error 89 ms 65536 KB Execution killed with signal 9
6 Runtime error 85 ms 65536 KB Execution killed with signal 9
7 Runtime error 1 ms 468 KB Execution killed with signal 11
8 Runtime error 1 ms 468 KB Execution killed with signal 11

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Runtime error 1 ms 468 KB Execution killed with signal 11
3 Runtime error 1 ms 468 KB Execution killed with signal 11
4 Runtime error 1 ms 468 KB Execution killed with signal 11
5 Runtime error 1 ms 468 KB Execution killed with signal 11
6 Runtime error 1 ms 468 KB Execution killed with signal 11
7 Incorrect 0 ms 340 KB Output isn't correct
8 Incorrect 0 ms 340 KB Output isn't correct
9 Runtime error 1 ms 456 KB Execution killed with signal 11
10 Runtime error 1 ms 468 KB Execution killed with signal 11
11 Runtime error 1 ms 460 KB Execution killed with signal 11
12 Runtime error 1 ms 468 KB Execution killed with signal 11

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -