Submission #1248371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248371		dfhdfhdsf	Papričice (COCI20_papricice)	C++20	50 / 110	1078 ms	523316 KiB

papricice

#include <bits/stdc++.h>
using namespace std;

int global_ans;
int n;
vector<vector<int>> graph;
vector<int> parent_arr;
vector<vector<int>> children_arr;
vector<int> size_arr;
vector<set<int>> res_sets;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    graph.resize(n+1);
    for (int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    parent_arr.assign(n+1, -1);
    children_arr.resize(n+1);
    vector<int> order;
    queue<int> q;
    q.push(1);
    parent_arr[1] = -1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : graph[u]) {
            if (v == parent_arr[u]) continue;
            parent_arr[v] = u;
            children_arr[u].push_back(v);
            q.push(v);
        }
    }
    reverse(order.begin(), order.end());

    size_arr.assign(n+1, 0);
    res_sets.resize(n+1);
    global_ans = 1e9;

    for (int u : order) {
        size_arr[u] = 1;
        vector<set<int>> branch_sets;
        for (int v : children_arr[u]) {
            size_arr[u] += size_arr[v];
            set<int> branch_set = res_sets[v];
            branch_set.insert(size_arr[v]);
            branch_sets.push_back(branch_set);
        }

        set<int> G;
        if (branch_sets.size() >= 2) {
            sort(branch_sets.begin(), branch_sets.end(), [](const set<int>& a, const set<int>& b) {
                return a.size() < b.size();
            });
            for (auto &bs : branch_sets) {
                for (int a : bs) {
                    if (!G.empty()) {
                        int total_rest = n - a;
                        double target_val = total_rest / 2.0;
                        auto it = G.lower_bound(target_val);
                        if (it != G.end()) {
                            int b = *it;
                            int s1 = a;
                            int s2 = b;
                            int s3 = n - a - b;
                            int max_val = max({s1, s2, s3});
                            int min_val = min({s1, s2, s3});
                            int gap = max_val - min_val;
                            if (gap < global_ans) global_ans = gap;
                        }
                        if (it != G.begin()) {
                            auto it_prev = prev(it);
                            int b = *it_prev;
                            int s1 = a;
                            int s2 = b;
                            int s3 = n - a - b;
                            int max_val = max({s1, s2, s3});
                            int min_val = min({s1, s2, s3});
                            int gap = max_val - min_val;
                            if (gap < global_ans) global_ans = gap;
                        }
                    }
                }
                for (int a : bs) {
                    G.insert(a);
                }
            }
        } else if (branch_sets.size() == 1) {
            G = branch_sets[0];
        }

        if (parent_arr[u] != -1) {
            int T = size_arr[u];
            int x = n - T;
            vector<double> targets = { (double)n/3, (double)T - (double)n/3, (double)T/2 };
            for (double target_val : targets) {
                auto it = G.lower_bound(target_val);
                if (it != G.end()) {
                    int a = *it;
                    int max_val = max({x, a, T - a});
                    int min_val = min({x, a, T - a});
                    int gap = max_val - min_val;
                    if (gap < global_ans) global_ans = gap;
                }
                if (it != G.begin()) {
                    auto it_prev = prev(it);
                    int a = *it_prev;
                    int max_val = max({x, a, T - a});
                    int min_val = min({x, a, T - a});
                    int gap = max_val - min_val;
                    if (gap < global_ans) global_ans = gap;
                }
            }
        }

        res_sets[u] = move(G);
    }

    cout << global_ans << endl;

    return 0;
}

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