Submission #1288593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288593		Hamed_Ghaffari	Village (BOI20_village)	C++20	25 / 100	1094 ms	12888 KiB

Village

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

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

const int MXN = 1e5+5;

int n, h[MXN], par[MXN], ord[MXN], sz[MXN], ans_mn, p_mn[MXN], p_mx[MXN];
ll ans_mx;
bool mark[MXN], vis[MXN];
vector<int> g[MXN], G[MXN];

void dfs1(int v) {
    sz[v] = 1;
    for(int u : g[v])
        if(u!=par[v]) {
            par[u] = v;
            h[u] = h[v]+1;
            dfs1(u);
            sz[v] += sz[u];
        }
}

vector<int> vec;

void dfs2(int v) {
    vec.push_back(v);
    vis[v] = 1;
    for(int u : G[v])
        if(!vis[u])
            dfs2(u);
}

int centroid(int v) {
    for(int u : g[v])
        if(u!=par[v] && sz[u]+sz[u]>n)
            return centroid(u);
    return v;
}

void dfs3(int v, int p=0) {
    vec.push_back(v);
    for(int u : g[v])
        if(u!=p)
            dfs3(u, v);
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=0,u,v; i<n-1; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1);
    iota(ord+1, ord+n+1, 1);
    sort(ord+1, ord+n+1, [&](int u, int v) {
        return h[u]>h[v];
    });
    for(int i=1; i<=n; i++) {
        int v = ord[i];
        if(mark[v]) continue;
        ans_mn += 2;
        if(h[v]==0) {
            G[v].push_back(g[v][0]);
            G[g[v][0]].push_back(v);
        }
        else {
            G[v].push_back(par[v]);
            G[par[v]].push_back(v);
            mark[par[v]] = 1;
        }
    }
    for(int i=1; i<=n; i++) if(!vis[i]) {
        dfs2(i);
        for(int j=0; j<SZ(vec); j++)
            p_mn[vec[j]] = vec[(j+1)%SZ(vec)];
    }

    for(int i=1; i<=n; i++) ans_mx += 2*min(sz[i], n-sz[i]);
    vec.clear();
    dfs3(centroid(1));
    if(n&1) {
        p_mx[vec[0]] = vec[1];
        p_mx[vec[1]] = vec[1+n/2];
        p_mx[vec[1+n/2]] = vec[0];
        for(int i=2; i+n/2<n; i++)
            p_mx[vec[i]] = vec[i+n/2],
            p_mx[vec[i+n/2]] = vec[i];
    }
    else {
        for(int i=0; i+n/2<n; i++)
            p_mx[vec[i]] = vec[i+n/2],
            p_mx[vec[i+n/2]] = vec[i];
    }

    cout << ans_mn << ' ' << ans_mx << '\n';
    for(int i=1; i<=n; i++) cout << p_mn[i] << ' ';
    cout << '\n';
    for(int i=1; i<=n; i++) cout << p_mx[i] << ' ';
    cout << '\n';
    return 0;
}

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 0 / 50