Submission #487978

#	Time	Username	Problem	Language	Result	Execution time	Memory
487978		KazamaHoang	Papričice (COCI20_papricice)	C++14	110 / 110	235 ms	29204 KiB

papricice

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9 + 69;

bool ckmin(int& a, int b) {
    return a > b? a = b, true : false;
}

int n;
vector<int> adj[200005];
multiset<int> ancestor, other;
int d[200005];
int res = inf;

void dfs(int u, int par = -1) {
    d[u] = 1;
    for (int& v : adj[u]) if (v != par) {
        dfs(v, u);
        d[u] += d[v];
    }
}

void DFS(int u, int par = -1) {
    // 2 node la to tien cua nhau
    if (u != 1) {
        auto it = ancestor.lower_bound(n+d[u]);
        if (it != ancestor.end()) {
            int s = *it; s /= 2;
            int part_one = d[u];
            int part_two = n - s;
            int part_three = s - d[u];
            int mx = max({part_one, part_two, part_three});
            int mn = min({part_one, part_two, part_three});
            ckmin(res, mx - mn);
        }
        if (it != ancestor.begin()) {
            -- it;
            int s = *it; s /= 2;
            int part_one = d[u];
            int part_two = n - s;
            int part_three = s - d[u];
            int mx = max({part_one, part_two, part_three});
            int mn = min({part_one, part_two, part_three});
            ckmin(res, mx - mn);
        }        
    }

    // 2 node khong phai to tien cua nhau
    if (u != 1) {
        auto it = other.lower_bound(n-d[u]);
        if (it != other.end()) {
            int s = *it; s /= 2;
            int part_one = d[u];
            int part_two = s;
            int part_three = n - d[u] - s;
            int mx = max({part_one, part_two, part_three});
            int mn = min({part_one, part_two, part_three});
            ckmin(res, mx - mn); 
        }
        if (it != other.begin()) {
            -- it;
            int s = *it; s /= 2;
            int part_one = d[u];
            int part_two = s;
            int part_three = n - d[u] - s;
            int mx = max({part_one, part_two, part_three});
            int mn = min({part_one, part_two, part_three});
            ckmin(res, mx - mn);
        }
    }
    ancestor.insert(2*d[u]);
    for (int& v : adj[u]) if (v != par) 
        DFS(v, u);
    ancestor.erase(ancestor.find(2*d[u]));
    other.insert(2*d[u]);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i < n; ++ i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, -1);
    DFS(1, -1);
    cout << res;
    return 0;
}

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