oj.uz

Submission #986527

# Submission time Handle Problem Language Result Execution time Memory
986527 2024-05-20T17:55:59 Z HiepVu217 Papričice (COCI20_papricice) C++17
110 / 110
 205 ms 28496 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)
{
    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.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4960 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4960 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 142 ms 21652 KB Output is correct
12 Correct 205 ms 21588 KB Output is correct
13 Correct 137 ms 22352 KB Output is correct
14 Correct 152 ms 21844 KB Output is correct
15 Correct 201 ms 21516 KB Output is correct
16 Correct 133 ms 24232 KB Output is correct
17 Correct 141 ms 24140 KB Output is correct
18 Correct 166 ms 28496 KB Output is correct
19 Correct 130 ms 24256 KB Output is correct
20 Correct 150 ms 24044 KB Output is correct