Submission #1099312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099312		MateiKing80	Village (BOI20_village)	C++14	100 / 100	43 ms	25544 KiB

Village

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

#define int long long
#define ll long long
#define ar array
#define ld long double

const int N = 3e5 + 20;
const int K = 200;
const int INF = 1e15;
const int LOG = 24;
const int MOD = 998244353;

vector<int> g[N], ord;
int n, posLo[N], posHi[N], ansLo, ansHi, sz[N];

void dfs(int x,int p)
{
    sz[x] = 1;
    ord.push_back(x);
    for(auto u: g[x])
    {
        if(u == p)
            continue;
        dfs(u, x);
        sz[x] += sz[u];
        ansHi += min(sz[u], n - sz[u]);
    }
    if(posLo[x] == x)
    {
        if(p == -1)
            swap(posLo[x], posLo[g[x][0]]);
        else
            swap(posLo[x], posLo[p]);
        ansLo += 2;
    }

}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin>>u>>v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for(int i = 0; i < n; i ++)
        posLo[i] = i;
    dfs(0, -1);
    ansHi *= 2;
    for(int i = 0; i < n; i++)
    {
        int u = ord[i];
        int v = ord[(i + n / 2) % n];
        posHi[u] = v;
    }
    cout << ansLo << " " << ansHi << '\n';
    for(int i = 0; i < n; i ++)
        cout << posLo[i] + 1 << " ";
    cout << '\n';
    for(int i = 0; i < n; i ++)
        cout << posHi[i] + 1 << " ";
}

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