Submission #964336

#	Time	Username	Problem	Language	Result	Execution time	Memory
964336		codefox	Village (BOI20_village)	C++14	100 / 100	72 ms	24028 KiB

Village

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")

#define int long long

vector<vector<int>> graph;
vector<int> subsize;
vector<int> subtree;
int cent = -1;
int ds = 0;
int n;

vector<int> match;
vector<int> matched;
int dds = 0;

void dp(int i, int p)
{
    vector<int> nodes;
    for (int ele:graph[i])
    {
        if (ele == p) continue;
        dp(ele, i);
        if (matched[ele]==0) nodes.push_back(ele);
    }
    if (nodes.size()==0) return;
    dds += nodes.size()*2;
    match[i] = nodes[0];
    for (int j = 0; j < nodes.size()-1; j++)
    {
        match[nodes[j]] = nodes[j+1];
    }
    match[nodes.back()] = i;
    matched[i] = 1;
}

void dfs(int i, int p)
{
    int sum = 0;
    bool b = 1;
    for (int ele:graph[i])
    {
        if (ele == p) continue;
        dfs(ele, i);
        if (subsize[ele]*2>n) b = 0;
        subsize[i] += subsize[ele];
        sum += subsize[ele];
    }
    sum = n-sum-1;
    if (sum*2>n) b=0;
    if (b) cent = i;
    subsize[i]++;
}

void dist(int i, int p, int d)
{
    for (int ele:graph[i])
    {
        if (ele == p) continue;
        dist(ele, i, d+1);
    }
    ds += d;
}

void sub(int i, int p)
{
    subtree.push_back(i);
    for (int ele:graph[i])
    {
        if (ele == p) continue;
        sub(ele, i);
    }
}

bool comp(vector<int> &a, vector<int> &b)
{
    if (a.size() > b.size()) return 1;
    else return 0;
}

int32_t main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    graph.assign(n, vector<int>());
    subsize.assign(n, 0);
    match.assign(n, 0);
    matched.assign(n, 0);

    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(0, -1);
    dp(0, -1);
    if (!matched[0])
    {
        dds+=2;
        int ele = graph[0].back();
        match[0] = match[ele];
        match[ele] = 0;
    }

    int mx = -1;

    dist(cent, -1, 0);
    mx = ds*2;

    vector<vector<int>> subs;
    for (int i = 0; i < graph[cent].size(); i++)
    {
        sub(graph[cent][i], cent);
        subs.push_back(subtree);
        subtree.clear();
    }
    subs.push_back(vector<int>(1, cent));
    sort(subs.begin(), subs.end(), comp);

    cout << dds << " " << mx << endl;

    vector<int> left;
    vector<int> ini;
    vector<int> part(n, 0);
    for (auto ele:subs)
    {
        for (int e:ele) 
        {
            ini.push_back(e);
            left.push_back(e);
        }
    }
    for (int i = 0; i < subs[0].size(); i++)
    {
        part[ini[i]] = left.back();
        left.pop_back();
    }
    int i = subs[0].size();
    for (int ele:left) 
    {
        part[ini[i]] = ele;
        i++;
    }
    for (int i = 0; i <n; i++) cout << match[i]+1 << " ";
    cout << endl;
    for (int ele:part) cout << ele+1 << " ";
}

Compilation message (stderr)

Village.cpp: In function 'void dp(long long int, long long int)':
Village.cpp:32:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int j = 0; j < nodes.size()-1; j++)
      |                     ~~^~~~~~~~~~~~~~~~
Village.cpp: In function 'int32_t main()':
Village.cpp:124:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for (int i = 0; i < graph[cent].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
Village.cpp:146:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for (int i = 0; i < subs[0].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~

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