제출 #475470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
475470		Shin	Village (BOI20_village)	C++17	100 / 100	124 ms	20152 KiB

Village

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK "task"
#define all(x) x.begin(), x.end()

using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7; // 998244353;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;

typedef long long ll;
typedef unsigned long long ull;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

int n;
vector<int> adj[N];

namespace task1 {
    static int best = 0;
    static int newHouse[N];
    void dfs(int u, int p) {
        for (int v: adj[u]) if (v != p) {
            dfs(v, u);
            if (v == newHouse[v]) {
                best += 2;
                swap(newHouse[u], newHouse[v]);
            }
        }
    }
     
    void solve(void) {
        for (int i = 1; i <= n; i ++) newHouse[i] = i;
        dfs(1, 1);
        if (newHouse[1] == 1) {
            best += 2;
            swap(newHouse[1], newHouse[*adj[1].begin()]);
        }
    }
}

namespace task2 {
    static ll best;
    static int sub[N];
    static int newHouse[N];
    vector<int> vertex;

    void dfs1(int u, int p) {
        sub[u] = 1;
        vertex.push_back(u);
        for (int v: adj[u]) if (v != p) {
            dfs1(v, u);
            sub[u] += sub[v];
            best += min(sub[v], n - sub[v]);
        }
    }

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

    void solve(void) {
        for (int i = 1; i <= n; i ++) newHouse[i] = i;
        dfs1(1, 1);
        int centerNode = centroid(1, 1);
        // cout << centerNode << '\n';
        dfs1(centerNode, centerNode);

        int mx = 0;
        for (int v: adj[centerNode]) maximize(mx, sub[v]);
        for (int i = 0; i < n; i ++) 
            newHouse[vertex[i]] = vertex[(i + mx) % n];
    }   
}

int main(void) {
    cin.tie(0)->sync_with_stdio(0); 
    int test = 1;
    // cin >> test;
    while (test --) {
        cin >> n;
        for (int i = 1; i < n; i ++) {
            int u, v; cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        task1::solve();
        task2::solve();
        cout << task1::best << " " << task2::best << '\n';
        for (int i = 1; i <= n; i ++) cout << task1::newHouse[i] << " \n"[i == n];
        for (int i = 1; i <= n; i ++) cout << task2::newHouse[i] << " \n"[i == n];
    }
    return 0;
}

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