CSES - Datatähti Open 2021 - Results
Submission details
Task:Distances
Sender:dxz05
Submission time:2021-01-30 11:12:38 +0200
Language:C++17
Status:READY
Result:29
Feedback
groupverdictscore
#1ACCEPTED29
#20
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#2--2details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:121:20: warning: statement has no effect [-Wunused-value]
         debug(test);
                    ^

Code

//#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.00001;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 1e6 + 3e1;
const int M = 122;

vector<int> g[M];

int dr[M];
int up[M][8], tin[M], tout[M], timer = 0;
void dfs(int v, int p){
    tin[v] = ++timer;
    dr[v] = (v == 1 ? 0 : dr[p] + 1);
    up[v][0] = p;

    for (int i = 1; i < 8; i++) up[v][i] = up[up[v][i - 1]][i - 1];

    for (int u : g[v]){
        if (u != p) dfs(u, v);
    }

    tout[v] = ++timer;
}

bool upper(int a, int b){
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

int lca(int a, int b){
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;
    for (int i = 7; i >= 0; i--){
        if (!upper(up[a][i], b)) a = up[a][i];
    }
    return up[a][0];
}

int dist(int a, int b){
    return dr[a] + dr[b] - 2 * dr[lca(a, b)];
}

void solve(int TC) {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) g[i].clear();

    for (int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> v;
    for (int i = 1; i <= n; i++) v.push_back(i);

    dfs(1, 1);

    do {
        bool ok = true;
        for (int i = 1; i < n; i++){
            int x = v[i - 1], y = v[i];
            ok &= dist(x, y) <= 3;
        }
        if (ok){
            for (int i : v) cout << i << ' ';
            cout << endl;
            return;
        }
    } while (next_permutation(v.begin(), v.end()));

}

int main() {
    startTime = clock();
    ios_base::sync_with_stdio(false);

    bool llololcal = false;
#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    llololcal = true;
#endif

    int TC = 1;
    cin >> TC;

    for (int test = 1; test <= TC; test++) {
        debug(test);
        solve(test);
    }

    if (llololcal) cerr << endl << "Time: " << getCurrentTime() * 1000 << " ms" << endl;

    return 0;
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
100
8
5 2
2 3
3 7
...

correct output
1 8 2 5 6 7 3 4 
1 7 2 8 3 6 4 5 
1 4 6 2 7 5 8 3 
1 8 3 2 4 7 6 5 
1 6 4 7 5 2 3 8 
...

user output
1 3 2 4 7 5 6 8 
1 3 2 8 7 5 4 6 
1 3 2 5 7 8 6 4 
1 2 3 4 5 6 7 8 
1 3 2 4 6 8 7 5 
...

Test 2

Group: 2

Verdict:

input
100
100
37 59
81 37
44 81
...

correct output
1 99 82 81 59 5 71 55 17 24 13...

user output
(empty)