제출 #741552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
741552		Stickfish	Village (BOI20_village)	C++17	100 / 100	191 ms	17748 KiB

Village

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <numeric>
using namespace std;
using ll = long long;;

const int MAXN = 1e5 + 123;
vector<int> edg[MAXN];
bitset<MAXN> used;
int rt[MAXN];

bool dfs_getmark(int v, bitset<MAXN>& mark) {
    bool is_edge = false;
    for (auto u : edg[v]) {
        if (u == rt[v])
            continue;
        rt[u] = v;
        is_edge |= dfs_getmark(u, mark);
    }
    if (v == 0) {
        mark[v] = 1;
        if (is_edge)
            return true;
        for (auto u : edg[v]) {
            if (u == rt[v])
                continue;
            mark[u] = 0;
            return true;
        }
    }
    if (is_edge)
        mark[v] = 1;
    return !is_edge;
}

void dfs_onmark(int v, bitset<MAXN>& mark, vector<int>& ans) {
    ans.push_back(v);
    for (auto u : edg[v]) {
        if (u == rt[v] || mark[u])
            continue;
        dfs_onmark(u, mark, ans);
    }
}

pair<int, vector<int>> solve_min(int n) {
    used = 0;
    bitset<MAXN> mark;
    dfs_getmark(0, mark);
    vector<int> ans(n);
    for (int i = 0; i < n; i = mark._Find_next(i)) {
        vector<int> ccl;
        dfs_onmark(i, mark, ccl);
        int m = ccl.size();
        for (int j = 0; j < m; ++j) {
            ans[ccl[j]] = ccl[(j + 1) % m];
        }
    }
    return {2 * (n - mark.count()), ans};
}

int depth[MAXN];
int sz[MAXN];

void init_dfs(int v) {
    sz[v] = 1;
    for (auto u : edg[v]) {
        if (u == rt[v])
            continue;
        rt[u] = v;
        depth[u] = depth[v] + 1;
        init_dfs(u);
        sz[v] += sz[u];
    }
}

int find_centroid(int v) {
    for (auto u : edg[v]) {
        if (u == rt[v])
            continue;
        if (sz[u] * 2 > sz[0])
            return find_centroid(u);
    }
    return v;
}

void dfs_tin(int v, vector<int>& ans) {
    ans.push_back(v);
    for (auto u : edg[v]) {
        if (u == rt[v])
            continue;
        dfs_tin(u, ans);
    }
}

pair<ll, vector<int>> solve_max(int n) {
    used = 0;
    for (int i = 0; i < n; ++i)
        rt[i] = -1;
    init_dfs(0);
    int ctr = find_centroid(0);
    for (int i = 0; i < n; ++i)
        rt[i] = -1;
    depth[ctr] = 0;
    init_dfs(ctr);
    vector<int> tin;
    dfs_tin(ctr, tin);
    vector<int> ans(n);
    ll smd = 0;
    //for (auto x : tin)
        //cout << x + 1 << ' ';
    //cout << endl;
    for (int i = 0; i < n; ++i) {
        ans[tin[i]] = tin[(i + n / 2) % n];
        smd += depth[i];
    }
    return {smd * 2, ans};
}

signed main() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edg[u].push_back(v);
        edg[v].push_back(u);
    }
    auto ansmn = solve_min(n);
    auto ansmx = solve_max(n);
    cout << ansmn.first << ' ' << ansmx.first << '\n';
    for (auto x : ansmn.second)
        cout << x + 1 << ' ';
    cout << '\n';
    for (auto x : ansmx.second)
        cout << x + 1 << ' ';
    cout << '\n';
}

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