oj.uz

Submission #575894

# Submission time Handle Problem Language Result Execution time Memory
575894 2022-06-11T14:00:56 Z eecs Papričice (COCI20_papricice) C++17
110 / 110
 248 ms 48496 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200010;
int n, ans = INT_MAX, sz[maxn], fa[maxn];
vector<int> G[maxn];
set<int> V[maxn];
multiset<int> T;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }
    auto chk = [&](int a, int b) {
        int c = n - a - b;
        if (a && b && c) ans = min(ans, max({a, b, c}) - min({a, b, c}));
    };
    auto dfs1 = [&](auto self, int u) -> void {
        sz[u] = 1;
        for (int v : G[u]) if (v ^ fa[u]) {
            fa[v] = u, self(self, v), sz[u] += sz[v];
            vector<int> V1, V2;
            auto it = V[u].lower_bound((n + 2) / 3);
            if (it != V[u].end()) V1.push_back(*it);
            if (it != V[u].begin()) V1.push_back(*prev(it));
            it = V[v].lower_bound((n + 2) / 3);
            if (it != V[v].end()) V2.push_back(*it);
            if (it != V[v].begin()) V2.push_back(*prev(it));
            for (int x : V1) for (int y : V2) chk(x, y);
            if (V[u].size() < V[v].size()) swap(V[u], V[v]);
            for (int x : V[v]) V[u].insert(x);
        }
        V[u].insert(sz[u]);
        auto it = V[u].lower_bound(sz[u] / 2);
        chk(*it, sz[u] - *it);
        if (it != V[u].begin()) chk(*prev(it), sz[u] - *prev(it));
    };
    auto dfs2 = [&](auto self, int u) -> void {
        T.insert(n - sz[u]);
        for (int v : G[u]) if (v ^ fa[u]) {
            auto it = T.lower_bound((n - sz[v]) / 2);
            if (it != T.end()) chk(*it, n - sz[v] - *it);
            if (it != T.begin()) chk(*prev(it), n - sz[v] - *prev(it));
            self(self, v);
        }
        T.erase(T.find(n - sz[u]));
    };
    dfs1(dfs1, 1), dfs2(dfs2, 1);
    cout << ans << "\n";
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14424 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14424 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14632 KB Output is correct
7 Correct 8 ms 14604 KB Output is correct
8 Correct 9 ms 14600 KB Output is correct
9 Correct 9 ms 14548 KB Output is correct
10 Correct 9 ms 14548 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14424 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14632 KB Output is correct
7 Correct 8 ms 14604 KB Output is correct
8 Correct 9 ms 14600 KB Output is correct
9 Correct 9 ms 14548 KB Output is correct
10 Correct 9 ms 14548 KB Output is correct
11 Correct 248 ms 35948 KB Output is correct
12 Correct 244 ms 36556 KB Output is correct
13 Correct 205 ms 35652 KB Output is correct
14 Correct 225 ms 36100 KB Output is correct
15 Correct 234 ms 36588 KB Output is correct
16 Correct 154 ms 34104 KB Output is correct
17 Correct 222 ms 36120 KB Output is correct
18 Correct 228 ms 48496 KB Output is correct
19 Correct 220 ms 36848 KB Output is correct
20 Correct 226 ms 36960 KB Output is correct