Submission #725283

#	Time	Username	Problem	Language	Result	Execution time	Memory
725283		_martynas	Village (BOI20_village)	C++14	100 / 100	136 ms	17752 KiB

Village

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()

using pii = pair<int, int>;
using vi = vector<int>;
using ll = long long;

const int MXN = 1e5+5;

int n;
vi adj[MXN];
int deg[MXN];
int mn_ans[MXN], mx_ans[MXN];
ll mn_swap, mx_swap;
int sz[MXN], H[MXN];

void dfs(int u, int p) {
    sz[u] = 1;
    for(int v : adj[u]) if(v != p) {
        dfs(v, u); sz[u] += sz[v];
    }
}

int centroid(int u, int p) {
    for(int v : adj[u]) if(v != p) {
        if(2*sz[v] > n) return centroid(v, u);
    }
    return u;
}

void dfs1(int u, int p, vi &arr) {
    H[u] = H[p]+1;
    arr.PB(u);
    for(int v : adj[u]) if(v != p) dfs1(v, u, arr);
}

int main() {
    cin >> n;
    for(int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        adj[a].PB(b);
        adj[b].PB(a);
        deg[a]++, deg[b]++;
    }
    {
        // min
        queue<int> Q;
        for(int i = 1; i <= n; i++) {
            if(deg[i] == 1) {
                Q.push(i);
            }
        }
        iota(mn_ans+1, mn_ans+n+1, 1);
        while(!Q.empty()) {
            int i = Q.front(); Q.pop();
            if(i != mn_ans[i]) continue;
            deg[i] = 0;
            bool found = false;
            for(int j : adj[i]) {
                if(deg[j] > 0) {
                    deg[j] = 0; found = true;
                    for(int t : adj[j]) {
                        if(deg[t] > 0) {
                            deg[t]--;
                            if(deg[t] == 1) {
                                Q.push(t);
                            }
                        }
                    }
                    swap(mn_ans[i], mn_ans[j]);
                    mn_swap += 2;
                    break;
                }
            }
            if(!found) {
                int j = adj[i].back();
                swap(mn_ans[i], mn_ans[j]);
                mn_swap += 2;
            }
        }
    }
    {
        // max
        dfs(1, 1);
        int c = centroid(1, -1);
        vi arr = {c};
        for(int u : adj[c]) {
            dfs1(u, c, arr);
        }
        for(int i = 1; i <= n; i++) {
            mx_swap += 2*H[i];
        }
        for(int i = 0; i < n; i++) {
            mx_ans[arr[i]] = arr[(i+(n+1)/2)%n];
        }
    }
    cout << mn_swap << " " << mx_swap << "\n";
    for(int i = 1; i <= n; i++) cout << mn_ans[i] << " \n"[i == n];
    for(int i = 1; i <= n; i++) cout << mx_ans[i] << " \n"[i == n];
    return 0;
}

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