제출 #555264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
555264		ddy888	Village (BOI20_village)	C++17	50 / 100	110 ms	21312 KiB

Village

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef tuple<int,int,int> ti;  
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 100010;
int n, c, cnt;
vector<int> g[MAXN], nodes;
int minans, maxans;
int par[MAXN];
int sz[MAXN];
int vis[MAXN];
int pos[MAXN], dep[MAXN];
int mnc[MAXN], mxc[MAXN];
int group[MAXN];
vector<int> cent;

void getsz(int x, int fa) {
    sz[x] = 1;
    par[x] = fa;
    dep[x] = dep[fa] + 1;
    for (auto i: g[x]) {
        if (i == fa) 
            continue;
        getsz(i, x);
        sz[x] += sz[i];
    }
}

int centroid(int x, int fa) {
    for (auto i: g[x]) {
        if (i == fa)
            continue;
        if (sz[i] * 2 > n)
            return centroid(i, x);
    }
    return x;
}

void dfs(int x, int fa, int branch) {
    group[x] = branch;
    for (auto i: g[x]) {
        if (i == fa)
            continue;
        if (x == c) 
            dfs(i, x, ++cnt);
        else 
            dfs(i, x, branch);
    }
}

signed main() {
    fast;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    getsz(1, 1);
    c = centroid(1, 1);
    // Minimum
    for (int i = 1; i <= n; ++i) { 
        nodes.pb(i);
        pos[i] = i;
    }
    sort(nodes.begin(), nodes.end(), [](int a, int b) {
        return sz[a] < sz[b];
    });
    for (auto i: nodes) {
        if (vis[i])
            continue;
        bool ok = false;
        for (auto j: g[i]) {
            if (vis[j])
                continue;
            minans += 2, vis[j] = 1, ok = true;
            swap(pos[i], pos[j]);
            break;
        }
        if (!ok) {
            minans += 2;
            swap(pos[i], pos[par[i]]);
            if (i == par[i])
                swap(pos[i], pos[g[i].back()]);
        }
        vis[i] = 1;
    }
    for (int i = 1; i <= n; ++i)
        mnc[pos[i]] = i;

    // Maximum
    getsz(c, c);
    for (int i = 1; i <= n; ++i) {
        for (auto j: g[i]) {
            int hi = i, lo = j;
            if (dep[i] > dep[j])
                swap(lo, hi);
            maxans += min(n - sz[lo] + 1, sz[lo]);
        }
    }
    dfs(c, c, cnt );
    sort(nodes.begin(), nodes.end(), [](int a, int b) {
        return group[a] < group[b];
    });
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= n; ++i)
        pos[i] = i;
    int j = 1;
    for (int i = 1; i < n; ++i) {
        if (vis[nodes[i]] || vis[nodes[j]])
            continue;
        j = max(j, i);
        while (group[nodes[i]] == group[nodes[j]])
            ++j;
        if (j >= n)
            break;
        swap(pos[nodes[i]], pos[nodes[j]]);
        vis[nodes[i]] = 1, vis[nodes[j]] = 1;
        ++j;
    }
    if (n % 2) 
        swap(pos[nodes.back()], pos[c]);
    else {
        for (int i = 1; i < n; ++i) {
            if (!vis[nodes[i]]) {
                swap(pos[c], pos[nodes[i]]);
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        mxc[pos[i]] = i;

    cout << minans << ' ' << maxans << '\n';
    for (int i = 1; i <= n; ++i)
        cout << mnc[i] << ' ';
    cout << '\n';
    for (int i = 1; i <= n; ++i)
        cout << mxc[i] << ' ';
    return 0;
}

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50