Submission #1312826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312826		nxk02102010	Village (BOI20_village)	C++20	100 / 100	46 ms	16432 KiB

Village

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100005;
vector<int> g[N];
int s[N];
ll min_sum = 0;
void dfs_min(int u, int p){
    for(int v : g[u]){
        if(v == p) continue;
        dfs_min(v, u);
    }
    if(s[u] == u && p != 0){
        swap(s[u], s[p]);
        min_sum += 2;
    }
}
int dfn[N], id[N], sz[N], timer = 0;
ll max_sum = 0;
int n;
void dfs_max(int u, int p){
    dfn[u] = ++timer;
    id[timer] = u;
    sz[u] = 1;
    for(int v : g[u]){
        if(v == p) continue;
        dfs_max(v, u);
        sz[u] += sz[v];
        max_sum += 2LL * min(sz[v], n - sz[v]);
    }
}
int main(){
    //freopen("Village.Inp","r",stdin);
    //freopen("Village.Out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for(int i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i = 1; i <= n; i++) s[i] = i;
    dfs_min(1, 0);

    if(s[1] == 1){ 
        int v = g[1][0];
        swap(s[1], s[v]);
        min_sum += 2;
    }
    dfs_max(1, 0);
    vector<int> ans_max(n+1);
    for(int i = 1; i <= n; i++){
        ans_max[i] = id[(dfn[i] + n/2 - 1) % n + 1];
    }
    cout << min_sum << " " << max_sum << "\n";
    for(int i = 1; i <= n; i++)
        cout << s[i] << " ";
    cout << "\n";
    for(int i = 1; i <= n; i++)
        cout << ans_max[i] << " ";
    cout << "\n";

    return 0;
}

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