oj.uz

Submission #986511

# Submission time Handle Problem Language Result Execution time Memory
986511 2024-05-20T17:29:55 Z HiepVu217 Papričice (COCI20_papricice) C++17
15 / 110
 4 ms 5212 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5168 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5168 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 4 ms 5212 KB Output is correct
7 Incorrect 4 ms 5212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5168 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 4 ms 5212 KB Output is correct
7 Incorrect 4 ms 5212 KB Output isn't correct
8 Halted 0 ms 0 KB -