제출 #1273541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273541		cpismylifeOwO	Village (BOI20_village)	C++20	100 / 100	147 ms	34440 KiB

Village

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;
const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;

int n;
vector<int> graph[MaxN];

void Inp()
{
    cin >> n;
    for (int x = 1; x < n; x++)
    {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}

int sz[MaxN];

void PreDFS(int u, int p)
{
    sz[u] = 1;
    for (int x : graph[u])
    {
        if (x != p)
        {
            PreDFS(x, u);
            sz[u] += sz[x];
        }
    }
}

int FindCentroid(int u, int p)
{
    for (int x : graph[u])
    {
        if (x != p && sz[x] > (n / 2))
        {
            return FindCentroid(x, u);
        }
    }
    return u;
}

int cur;
int group[MaxN];
int cnt[MaxN];
int permmx[MaxN];
int d[MaxN];

void DFSmx(int u, int p)
{
    for (int v : graph[u])
    {
        if (v != p)
        {
            if (p == -1)
            {
                cur++;
                cnt[cur]++;
                group[v] = cur;
            }
            else
            {
                cnt[group[u]]++;
                group[v] = group[u];
            }
            d[v] = d[u] + 1;
            DFSmx(v, u);
        }
    }
}

int id[MaxN];

bool cmp(int a, int b)
{
    if (cnt[group[a]] == cnt[group[b]])
    {
        return group[a] < group[b];
    }
    return cnt[group[a]] > cnt[group[b]];
}

struct Best
{
    int r0, r1, r2;

    Best(int _r0, int _r1, int _r2)
    {
        r0 = _r0;
        r1 = _r1;
        r2 = _r2;
    }
};

int permin[MaxN];
int F[3][MaxN];
vector<Best> track[MaxN];
bool haschild[MaxN];

void DFSmi(int u, int p)
{
    F[0][u] = inf;
    F[1][u] = inf;
    F[2][u] = 0;
    for (int x : graph[u])
    {
        if (x != p)
        {
            DFSmi(x, u);
            haschild[u] = true;
            int pre0 = F[0][u], pre1 = F[1][u], pre2 = F[2][u];
            Best tracking = Best(0, 0, 2);
            F[0][u] = min(min(pre0 + F[0][x], pre1 + F[1][x] + 2), inf);
            F[1][u] = min(min(pre0 + F[1][x] + 2, min(pre1 + F[0][x], pre2 + F[1][x] + 2)), inf);
            F[2][u] = min(pre2 + F[0][x], inf);
            if (pre0 + F[0][x] > pre1 + F[1][x] + 2)
            {
                tracking.r0 = 1;
            }
            if (F[1][u] == pre1 + F[0][x])
            {
                tracking.r1 = 1;
            }
            else if (F[1][u] == pre2 + F[1][x] + 2)
            {
                tracking.r1 = 2;
            }
            track[u].push_back(tracking);
        }
    }
    Best tracking = Best(1, 0, 2);
    int pre0 = F[0][u], pre1 = F[1][u], pre2 = F[2][u];
    F[0][u] = pre1;
    F[1][u] = min(pre0, pre2);
    F[2][u] = pre2;
    if (haschild[u])
    {
        if (F[0][u] > pre0)
        {
            F[0][u] = pre0;
            tracking.r0 = 0;
        }
        if (F[0][u] > pre2 + 2)
        {
            F[0][u] = min(pre2 + 2, inf);
            tracking.r0 = 2;
        }
    }
    if (pre0 > pre2)
    {
        tracking.r1 = 2;
    }
    track[u].push_back(tracking);
}

int Track(int u, int par, int cur)
{
    vector<int> sw;
    int issw = 0;
    if (cur == 0 && track[u].back().r0 != 1)
    {
        if (track[u].back().r0 == 0)
        {
            issw = 1;
            cur = 0;
        }
        else
        {
            issw = 2;
            cur = 2;
        }
    }
    else
    {
        sw.push_back(u);
        if (cur == 0)
        {
            cur = track[u].back().r0;
        }
        else
        {
            cur = track[u].back().r1;
        }
    }
    track[u].pop_back();
    int i = (int)track[u].size() - 1, p = -1;
    for (int x = (int)graph[u].size() - 1; x >= 0; x--)
    {
        int v = graph[u][x];
        if (v == par)
        {
            continue;
        }
        //cout << track[u][i].r0 << " " << track[u][i].r1 << " " << track[u][i].r2 << "\n";
        bool t = false;
        if (cur == 1)
        {
            t = (track[u][i].r1 == 0 || track[u][i].r1 == 2);
            cur = track[u][i].r1;
        }
        else if (cur == 0)
        {
            t = (track[u][i].r0 == 1);
            cur = track[u][i].r0;
        }
        i--;
        if (t)
        {
            sw.push_back(Track(v, u, true));
            if (issw == 1)
            {
                p = sw.back();
            }
        }
        else
        {
            Track(v, u, false);
        }
        if (issw == 2)
        {
            p = v;
        }
    }
    while ((int)sw.size() > 1)
    {
        int u = sw.back();
        sw.pop_back();
        int v = sw.back();
        sw.pop_back();
        permin[u] = v;
        permin[v] = u;
    }
    if (issw == 1)
    {
        permin[u] = u;
        swap(permin[u], permin[p]);
    }
    else if (issw == 2)
    {
        permin[u] = u;
        swap(permin[u], permin[p]);
    }
    if (sw.empty())
    {
        return 0;
    }
    return sw.back();
}

void Exc()
{
    PreDFS(1, -1);
    int root = FindCentroid(1, -1);
    DFSmx(root, -1);
    long long resmx = 0;
    for (int x = 1; x <= n; x++)
    {
        id[x] = x;
        resmx += d[x] * 2;
    }
    swap(id[n], id[root]);
    sort(id + 1, id + n, cmp);
    if (n & 1)
    {
        for (int x = 1; x + (n / 2) < n; x++)
        {
            permmx[id[x]] = id[x + (n / 2)];
            permmx[id[x + (n / 2)]] = id[x];
        }
        permmx[root] = root;
        swap(permmx[root], permmx[id[n - 1]]);
    }
    else
    {
        for (int x = 1; x + (n / 2) <= n; x++)
        {
            permmx[id[x]] = id[x + (n / 2)];
            permmx[id[x + (n / 2)]] = id[x];
        }
    }
    DFSmi(1, -1);
    Track(1, -1, 0);
    cout << F[0][1] << " " << resmx << "\n";
    for (int x = 1; x <= n; x++)
    {
        cout << permin[x] << " ";
    }
    cout << "\n";
    for (int x = 1; x <= n; x++)
    {
        cout << permmx[x] << " ";
    }
}

int main()
{
    //freopen("VILLAGE.INP", "r", stdin);
    //freopen("VILLAGE.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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