oj.uz

Submission #589762

# Submission time Handle Problem Language Result Execution time Memory
589762 2022-07-05T08:50:18 Z 박상훈(#8406) Island Traversal (FXCUP3_island) C++17
0 / 100
 17 ms 21464 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<int> adj[300300], G[300300], ans, P[300300];
int D;

void dfs(int s, int pa = -1, int dep = 1){
    D = max(D, dep);
    P[dep].push_back(s);
    for (auto &v:adj[s]) if (v!=pa){
        G[s].push_back(v);
        dfs(v, s, dep+1);
    }
}

int next_level(int d, int s){
    for (auto &x:P[d]) if (!G[x].empty()){
        ans.push_back(x);
        ans.push_back(G[x][0]);
        s = G[x][0];
    }
    return s;
}

void construct(int R){
    int s = R;
    ans.push_back(s);
    for (int i=D-1;i>2;i--){
        s = next_level(i, s);
    }
    ans.push_back(P[2][0]);
    ans.push_back(R);
}

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

    int rt = 0;
    for (int i=1;i<=n;i++) if (adj[i].size()==1) {rt = i; break;}

    dfs(rt);
    if (D<4) {printf("0\n"); return 0;}
    construct(rt);

    printf("%d\n", (int)ans.size()-1);
    for (auto &x:ans) printf("%d ", x);
    return 0;
}

Compilation message

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

Subtask #1
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 21460 KB Correct
2 Correct 12 ms 21464 KB Correct
3 Incorrect 11 ms 21460 KB Wrong
4 Halted 0 ms 0 KB -

Subtask #2
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 21460 KB Correct
2 Correct 12 ms 21464 KB Correct
3 Incorrect 11 ms 21460 KB Wrong
4 Halted 0 ms 0 KB -