Submission #1266395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266395		nguyenhuythach	Village (BOI20_village)	C++20	0 / 100	0 ms	324 KiB

Village

//cre: johutha
//greedy idea on cf tutorial 
#include <iostream>
#include <vector>
#include <algorithm>

#define int int64_t

using namespace std;

struct graph
{
    int n;
    vector<vector<int>> adjlist;
    vector<int> pre;
    vector<int> subtc;

    int d = 0;

    void dfs(int curr, int par)
    {
        pre.emplace_back(curr);
        subtc[curr] = 1;

        for (auto next : adjlist[curr])
        {
            if (next == par) continue;
            dfs(next, curr);
            subtc[curr] += subtc[next];
            d += 2*min(subtc[next], n - subtc[next]);
        }
    }

    void solve()
    {
        subtc.resize(n, 0);
        dfs(0, -1);
        cout << d << "\n";
        vector<int> sol(n);

        for (int i = 0; i < n; i++)
        {
            sol[pre[(i + n/2) % n]] = pre[i];
        }

        for (auto i : sol)
        {
            cout << i + 1 << " ";
        }
        cout << "\n";
    }
};

signed main()
{
    int n;
    cin >> n;

    graph g;
    g.n = n;
    g.adjlist.resize(n);

    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b; a--; b--;
        g.adjlist[a].push_back(b);
        g.adjlist[b].push_back(a);
    }

    g.solve();
}

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