Submission #575894

#	Time	Username	Problem	Language	Result	Execution time	Memory
575894		eecs	Papričice (COCI20_papricice)	C++17	110 / 110	248 ms	48496 KiB

papricice

#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 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60