Submission #547935

#	Time	Username	Problem	Language	Result	Execution time	Memory
547935		Jomnoi	Village (BOI20_village)	C++17	100 / 100	200 ms	25548 KiB

Village

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

const int MAX_N = 1e5 + 10;

int timer;
long long ans1, ans2;
int sz[MAX_N], depth[MAX_N], parent[MAX_N][20];
vector <int> graph[MAX_N];
int pos[MAX_N], nhouse1[MAX_N], nhouse2[MAX_N];

void dfs1(const int &u, const int &p) {
    for(auto v : graph[u]) {
        if(v != p) {
            dfs1(v, u);
        }
    }

    if(nhouse1[u] == u) {
        ans1 += 2;
        if(p != -1) {
            swap(nhouse1[u], nhouse1[p]);
        }
        else {
            swap(nhouse1[1], nhouse1[graph[1][0]]);
        }
    }
}

int get_size(const int &u, const int &p) {
    sz[u] = 1;
    for(auto v : graph[u]) {
        if(v != p) {
            sz[u] += get_size(v, u);
        }
    }
    return sz[u];
}

int get_centroid(const int &u, const int &p, const int &n) {
    for(auto v : graph[u]) {
        if(v != p and sz[v] > n / 2) {
            return get_centroid(v, u, n);
        }
    }
    return u;
}

void dfs2(const int &u, const int &p) {
    pos[++timer] = u;
    for(int i = 1; i < 20; i++) {
        parent[u][i] = parent[parent[u][i - 1]][i - 1];
    }
    for(auto v : graph[u]) {
        if(v == p) {
            continue;
        }

        depth[v] = depth[u] + 1;
        parent[v][0] = u;
        dfs2(v, u);
    }
}

int find_lca(const int &a, const int &b) {
    int u = a, v = b;
    if(depth[u] < depth[v]) {
        swap(u, v);
    }
    for(int i = 19; i >= 0; i--) {
        if(depth[parent[u][i]] >= depth[v]) {
            u = parent[u][i];
        }
    }
    for(int i = 19; i >= 0; i--) {
        if(parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return (u == v ? u : parent[u][0]);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int N;
    cin >> N;
    for(int i = 1; i <= N; i++) {
        nhouse1[i] = i;
    }
    for(int i = 1; i <= N - 1; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    dfs1(1, -1);
    dfs2(get_centroid(1, -1, get_size(1, -1)), -1);

    for(int i = 1; i <= N; i++) {
        nhouse2[pos[i]] = pos[(i + N / 2 - 1) % N + 1];
    }
    for(int i = 1; i <= N; i++) {
        ans2 += depth[i] + depth[nhouse2[i]] - 2 * depth[find_lca(i, nhouse2[i])];
    }

    cout << ans1 << ' ' << ans2 << '\n';
    for(int i = 1; i <= N; i++) {
        cout << nhouse1[i] << ' ';
    }
    cout << '\n';
    for(int i = 1; i <= N; i++) {
        cout << nhouse2[i] << ' ';
    }
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 38 / 38
• Subtask 3: 50 / 50