Submission #1153452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153452		antonn	Village (BOI20_village)	C++20	100 / 100	80 ms	17848 KiB

Village

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 7;

int n, sz[N];
vector<int> g[N];

ll sum_min = 0, sum_max = 0;
vector<int> mnmz, mxmz;

void dfs_min(int u, int p = 0) {
    for (auto v : g[u]) {
        if (v != p) {
            dfs_min(v, u);
            if (mnmz[v - 1] == v) {
                sum_min += 2;
                swap(mnmz[u - 1], mnmz[v - 1]);
            }
        }
    }
}

void solvemin() {
    mnmz.resize(n);
    iota(mnmz.begin(), mnmz.end(), 1);
    dfs_min(1);
    if (mnmz[0] == 1) {
        sum_min += 2;
        swap(mnmz[0], mnmz[g[1][0] - 1]);
    }
}

void calc(int u, int p = -1) {
    sz[u] = 1;
    for (auto v : g[u]) {
        if (v != p) {
            calc(v, u);
            sz[u] += sz[v];
            sum_max += 2 * min(n - sz[v], sz[v]);
        }
    }
}

int centr = -1;

int find_centroid(int u, int p = -1) {
    for (auto v : g[u]) {
        if (v != p && sz[v] > n / 2) {
            return find_centroid(v, u);
        }
    }
    return u;
}

vector<pair<int, int>> a, b;

void dfs(int u, int orig, int p) {
    a.push_back({orig, u});
    for (auto v : g[u]) {
        if (v != p) {
            dfs(v, orig, u);
        }
    }
}

void solvemax() {
    calc(1);
    centr = find_centroid(1);
    for (auto v : g[centr]) {
        dfs(v, v, centr);
    }
    a.push_back({n + 1, centr});
    b = a;
    sort(a.begin(), a.end());
    sort(b.rbegin(), b.rend());
    int repair = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i].first == b[i].first) {
            repair = a[i].first;
        }
    }
    vector<int> help;
    for (int i = 0; i < n; ++i) {
        if (a[i].first != repair && b[i].first != repair) {
            help.push_back(i);
        }
    }
    reverse(help.begin(), help.end());
    for (int i = 0; i < n; ++i) {
        if (a[i].first == b[i].first) {
            swap(a[help.back()], a[i]);
            help.pop_back();
        }
    }
    mxmz.resize(n);
    for (int i = 0; i < n; ++i) mxmz[a[i].second - 1] = b[i].second;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    solvemin();
    solvemax();
    cout << sum_min << " " << sum_max << "\n";
    for (auto x : mnmz) cout << x << " ";
    cout << "\n";
    for (auto x : mxmz) cout << x << " ";
    cout << "\n";
    return 0;
}

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