oj.uz

Submission #589780

# Submission time Handle Problem Language Result Execution time Memory
589780 2022-07-05T09:08:40 Z 박상훈(#8406) Island Traversal (FXCUP3_island) C++17
0 / 100
 20 ms 35572 KB 
#include <bits/stdc++.h>

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

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

mt19937 seed(1234658);
int add(int s){
    shuffle(E.begin(), E.end(), seed);
    for (auto iter=E.begin();iter!=E.end();iter++) if (s!=iter->first){
        if (mp[s].find(iter->first)==mp[s].end()){
            ans.push_back(iter->first);
            ans.push_back(iter->second);
            int ret = iter->second;
            E.erase(iter);
            return ret;
        }
    }
    return 0;
}

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]);
        for (int i=1;i<(int)G[x].size();i++) E.emplace_back(x, G[x][i]);
        s = G[x][0];

        while(true){
            int nxt = add(s);
            if (!nxt) break;
            s = nxt;
        }
    }
    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);
}

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

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

    assert(chk(ans));
    return 0;
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
island.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         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 20 ms 35564 KB Correct
3 Incorrect 17 ms 35572 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 20 ms 35564 KB Correct
3 Incorrect 17 ms 35572 KB Wrong
4 Halted 0 ms 0 KB -