Submission #986527

#	Time	Username	Problem	Language	Result	Execution time	Memory
986527		HiepVu217	Papričice (COCI20_papricice)	C++17	110 / 110	205 ms	28496 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)
{
    int a, b, c;

    auto x = in.lower_bound ((n + sz[u]) / 2);
    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())
    {
        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.lower_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())
    {
        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);
    }
    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);
    ans = 1e9;
    calc (1, 0);
    cout << ans;
}

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