Submission #986511

#	Time	Username	Problem	Language	Result	Execution time	Memory
986511		HiepVu217	Papričice (COCI20_papricice)	C++17	15 / 110	4 ms	5212 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 17;
int n, sz[N], ans, ti;
vector <int> adj[N];
multiset <int> in, out;
void dfs (int u, int pr)
{
    ++sz[u];
    for (int v: adj[u])
    {
        if (v == pr)
        {
            continue;
        }
        dfs (v, u);
        sz[u] += sz[v];
    }
}
void calc (int u, int pr)
{
    if (u > 1)
    {
        int a, b, c;
        auto x = out.lower_bound (sz[u]);
        out.erase (x);

        x = in.upper_bound ((n - sz[u]) / 2 + sz[u]);
        if (x != in.begin())
        {
            --x;
            a = n - *x, b = *x - sz[u], c = sz[u];
            ans = min (ans, max ({abs (a - b), abs (b - c), abs (c - a)}));
            ++x;
        }
        if (x != in.end())
        {
            ++x;
            if (x != in.end())
            {
                a = n - *x, b = *x - sz[u], c = sz[u];
                ans = min (ans, max ({abs (a - b), abs (b - c), abs (c - a)}));
            }
            --x;
        }
        if (x != in.end())
        {
            a = n - *x, b = *x - sz[u], c = sz[u];
            ans = min (ans, max ({abs (a - b), abs (b - c), abs (c - a)}));
        }

        x = out.upper_bound ((n - sz[u]) / 2);
        if (x != out.begin())
        {
            --x;
            a = n - *x - sz[u], b = *x, c = sz[u];
            ans = min (ans, max ({abs (a - b), abs (b - c), abs (c - a)}));
            ++x;
        }
        if (x != out.end())
        {
            ++x;
            if (x != out.end())
            {
                a = n - *x - sz[u], b = *x, c = sz[u];
                ans = min (ans, max ({abs (a - b), abs (b - c), abs (c - a)}));
            }
            --x;
        }
        if (x != out.end())
        {
            a = n - *x - sz[u], b = *x, c = sz[u];
            ans = min (ans, max ({abs (a - b), abs (b - c), abs (c - a)}));
        }

        in.insert (sz[u]);
    }

    for (int v: adj[u])
    {
        if (v == pr)
        {
            continue;
        }
        calc (v, u);
    }

    if (u > 1)
    {
        auto x = in.lower_bound (sz[u]);
        in.erase (x);
        out.insert (sz[u]);
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1, u, v; i < n; ++i)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs (1, 0);
    for (int i = 2; i <= n; ++i)
    {
        out.insert (sz[i]);
    }
    ans = 1e9;
    calc (1, 0);
    cout << ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60