Submission #512214

#	Time	Username	Problem	Language	Result	Execution time	Memory
512214		KoD	Papričice (COCI20_papricice)	C++17	110 / 110	260 ms	30024 KiB

papricice

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class F> struct RecLambda : private F {
    explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

void setmin(int& x, const int y) {
    x = std::min(x, y);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<vector<int>> graph(N);
    for (int i = 1; i < N; ++i) {
        int x, y;
        std::cin >> x >> y;
        x -= 1, y -= 1;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    vector<int> parent(N), subtree(N);
    RecLambda([&](auto&& dfs, const int u) -> void {
        subtree[u] = 1;
        for (const int v : graph[u]) {
            if (v != parent[u]) {
                parent[v] = u;
                dfs(v);
                subtree[u] += subtree[v];
            }
        }
    })(0);
    std::multiset<int> anc, other;
    int ans = N;
    RecLambda([&](auto&& dfs, const int u) -> void {
        {
            auto itr = anc.lower_bound((N + subtree[u]) / 2);
            if (itr != anc.end()) {
                const int a = subtree[u];
                const int b = *itr - a;
                const int c = N - *itr;
                setmin(ans, std::max({std::abs(a - b), std::abs(b - c), std::abs(c - a)}));
            }
            if (itr != anc.begin()) {
                --itr;
                const int a = subtree[u];
                const int b = *itr - a;
                const int c = N - *itr;
                setmin(ans, std::max({std::abs(a - b), std::abs(b - c), std::abs(c - a)}));
            }
        }
        {
            auto itr = other.lower_bound((N - subtree[u]) / 2);
            if (itr != other.end()) {
                const int a = subtree[u];
                const int b = *itr;
                const int c = N - a - b;
                setmin(ans, std::max({std::abs(a - b), std::abs(b - c), std::abs(c - a)}));
            }
            if (itr != other.begin()) {
                --itr;
                const int a = subtree[u];
                const int b = *itr;
                const int c = N - a - b;
                setmin(ans, std::max({std::abs(a - b), std::abs(b - c), std::abs(c - a)}));
            }
        }
        anc.insert(subtree[u]);
        for (const int v : graph[u]) {
            if (v != parent[u]) {
                dfs(v);
            }
        }
        anc.erase(anc.find(subtree[u]));
        other.insert(subtree[u]);
    })(0);
    std::cout << ans << '\n';
    return 0;
}

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