oj.uz

Submission #512214

# Submission time Handle Problem Language Result Execution time Memory
512214 2022-01-16T07:44:38 Z KoD Papričice (COCI20_papricice) C++17
110 / 110
 260 ms 30024 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 288 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 2 ms 428 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 540 KB Output is correct
10 Correct 2 ms 452 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 2 ms 428 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 540 KB Output is correct
10 Correct 2 ms 452 KB Output is correct
11 Correct 240 ms 24812 KB Output is correct
12 Correct 228 ms 24764 KB Output is correct
13 Correct 185 ms 25148 KB Output is correct
14 Correct 244 ms 25028 KB Output is correct
15 Correct 260 ms 24732 KB Output is correct
16 Correct 217 ms 24688 KB Output is correct
17 Correct 200 ms 24880 KB Output is correct
18 Correct 242 ms 30024 KB Output is correct
19 Correct 226 ms 24968 KB Output is correct
20 Correct 219 ms 24756 KB Output is correct