oj.uz

Submission #589766

# Submission time Handle Problem Language Result Execution time Memory
589766 2022-07-05T08:54:09 Z 박상훈(#8406) Island Traversal (FXCUP3_island) C++17
0 / 100
 18 ms 35540 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);
}

map<int, int> mp[300300];
bool chk(const vector<int> &ans){
    for (int i=0;i<(int)ans.size()-1;i++){
        int tmp = mp[ans[i]][ans[i+1]];
        if (tmp==-1 || ans[i]==ans[i+1]) return 0;
        if (tmp!=i%2) return 0;
        mp[ans[i]][ans[i+1]] = -1, mp[ans[i+1]][ans[i]] = -1;
    }
    return 1;
}

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);

        mp[x][y] = 1;
        mp[y][x] = 1;
    }

    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);

    assert(chk(ans));

    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:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
island.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35540 KB Correct
2 Correct 17 ms 35540 KB Correct
3 Incorrect 17 ms 35540 KB Wrong
4 Halted 0 ms 0 KB -

Subtask #2
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35540 KB Correct
2 Correct 17 ms 35540 KB Correct
3 Incorrect 17 ms 35540 KB Wrong
4 Halted 0 ms 0 KB -