제출 #1281510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281510		quangminh412	Village (BOI20_village)	C++17	100 / 100	158 ms	30160 KiB

Village

/*
  Ben Watson

  Quang Minh MasterDDDDD
*/

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

#define ll long long

const string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

// main program
const int maxn = 1e5 + 1;
const int maxbit = 17;

struct DSU
{
    vector<int> par, sz;
    int n;

    DSU(int n) : n(n)
    {
        par.resize(n + 1, 0);
        sz.resize(n + 1, 1);
        for (int i = 1; i <= n; i++)
            par[i] = i;
    }

    int find(int u) { return (u == par[u] ? u : par[u] = find(par[u])); }
    int get(int u) { return sz[find(u)]; }

    void merge(int u, int v)
    {
        u = find(u);
        v = find(v);
        if (u == v) return;
        if (sz[u] > sz[v])
            swap(u, v);
        sz[v] += sz[u];
        par[u] = v;
    }
};

vector<int> adj[maxn], comp_mx[maxn], comp_mn[maxn];
int par[maxbit][maxn], d[maxn], sz[maxn];
int used[maxn], ans_mx[maxn], ans_mn[maxn];
DSU dsu(maxn);
int n, centroid;

void DFS_SZ(int u, int p = -1)
{
    sz[u] = 1;
    for (int v : adj[u])
    {
        if (v == p)
            continue;
        DFS_SZ(v, u);
        sz[u] += sz[v];
    }
}
int find_centroid(int u, int p = -1)
{
    for (int v : adj[u])
    {
        if (v == p)
            continue;
        if (sz[v] > n / 2)
            return find_centroid(v, u);
    }
    return u;
}

void DFS(int u, int p = -1)
{
    sz[u] = 1;
    for (int v : adj[u])
    {
        if (v == p)
            continue;

        par[0][v] = u;
        d[v] = d[u] + 1;
        for (int i = 1; i < maxbit; i++)
            par[i][v] = par[i - 1][par[i - 1][v]];
        DFS(v, u);
        sz[u] += sz[v];
    }
}

int LCA(int u, int v)
{
    if (d[u] < d[v])
        swap(u, v);
    int k = d[u] - d[v];
    for (int i = 0; i < maxbit; i++)
        if (k >> i & 1)
            u = par[i][u];
    if (u == v) return u;
    for (int i = maxbit - 1; i >= 0; i--)
        if (par[i][u] != par[i][v])
        {
            u = par[i][u];
            v = par[i][v];
        }
    return par[0][u];
}

int dist(int u, int v) { return d[u] + d[v] - 2 * d[LCA(u, v)]; }

void DFS_COMP(int u, int p, int top)
{
    if (!used[u])
        comp_mx[top].push_back(u);
    for (int v : adj[u])
    {
        if (v == p)
            continue;
        DFS_COMP(v, u, top);
    }
}

void DFS_MN(int u, int p = -1)
{
    sz[u] = 1;
    for (int v : adj[u])
    {
        if (v == p)
            continue;

        DFS_MN(v, u);
        if (sz[v] == 0)
            continue;
        if (sz[v] == 1)
        {
            dsu.merge(u, v);
            sz[u] += sz[v];
        }
    }
}

void solve()
{
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    DFS_SZ(1);
    centroid = find_centroid(1);
    DFS(centroid);

    if (n & 1)
    {
        vector<pair<int, int>> proc;
        for (int v : adj[centroid])
            proc.push_back({sz[v], v});
        sort(proc.begin(), proc.end(), greater<pair<int, int>>());
        int u = proc[0].second, v = proc[1].second;
        used[u] = used[v] = used[centroid] = 1;
        ans_mx[u] = v;
        ans_mx[v] = centroid;
        ans_mx[centroid] = u;
    }

    vector<int> proc;
    for (int v : adj[centroid])
    {
        proc.push_back(v);
        DFS_COMP(v, centroid, v);
    }

    priority_queue<pair<int, int>> pq;
    if (!used[centroid])
    {
        pq.push({1, centroid});
        comp_mx[centroid].push_back(centroid);
    }
    for (int x : proc)
        pq.push({(int)comp_mx[x].size(), x});
    while ((int)pq.size() > 1)
    {
        int x = pq.top().second;
        pq.pop();
        int y = pq.top().second;
        pq.pop();
        if (comp_mx[x].empty())
            break;

        int u = comp_mx[x].back(), v = comp_mx[y].back();
        comp_mx[x].pop_back();
        comp_mx[y].pop_back();
        ans_mx[u] = v;
        ans_mx[v] = u;
        if (!comp_mx[x].empty())
            pq.push({(int)comp_mx[x].size(), x});
        if (!comp_mx[y].empty())
            pq.push({(int)comp_mx[y].size(), y});
    }
    ll res_mx = 0;
    for (int u = 1; u <= n; u++)
        res_mx += dist(u, ans_mx[u]);

    DFS_MN(1);
    if (dsu.get(1) == 1)
        dsu.merge(1, adj[1][0]);
    for (int i = 1; i <= n; i++)
        comp_mn[dsu.find(i)].push_back(i);

    int res_mn = 0;
    for (int i = 1; i <= n; i++)
    {
        int m = (int)comp_mn[i].size();
        if (m == 0)
            continue;
        if (m == 2)
            res_mn += 2;
        else
            res_mn += 2 + (m - 2) * 2;
        for (int j = 1; j < m; j++)
            ans_mn[comp_mn[i][j - 1]] = comp_mn[i][j];
        ans_mn[comp_mn[i][m - 1]] = comp_mn[i][0];
    }

    cout << res_mn << ' ' << res_mx << '\n';
    for (int i = 1; i <= n; i++)
        cout << ans_mn[i] << ' ';
    cout << '\n';
    for (int i = 1; i <= n; i++)
        cout << ans_mx[i] << ' ';
    cout << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

Village.cpp: In function 'int main()':
Village.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Village.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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