Submission #1016163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016163		vjudge1	Papričice (COCI20_papricice)	C++17	110 / 110	171 ms	19912 KiB

papricice

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

const int N = 2e5 + 10;
int n, sz[N], ans = 1e9;
vector<int> g[N];

void pre_dfs(int v, int p = -1){
    sz[v] = 1;
    for (int u : g[v]){
        if (u == p) continue;
        pre_dfs(u, v);
        sz[v] += sz[u];
    }
}

set<int> anc, non_anc;

void dfs(int v, int p = -1){
    auto lb = anc.lower_bound(sz[v] + (n - sz[v]) / 2);
    if (lb != anc.end()){
        int mx = max({sz[v], (*lb) - sz[v], n - (*lb)});
        int mn = min({sz[v], (*lb) - sz[v], n - (*lb)});
        ans = min(ans, mx - mn);
    }
    if (lb != anc.begin()){
        lb--;
        int mx = max({sz[v], (*lb) - sz[v], n - (*lb)});
        int mn = min({sz[v], (*lb) - sz[v], n - (*lb)});
        ans = min(ans, mx - mn);
    }

    lb = anc.lower_bound(sz[v] + (n - sz[v]) / 2 + 1);
    if (lb != anc.end()){
        int mx = max({sz[v], (*lb) - sz[v], n - (*lb)});
        int mn = min({sz[v], (*lb) - sz[v], n - (*lb)});
        ans = min(ans, mx - mn);
    }
    if (lb != anc.begin()){
        lb--;
        int mx = max({sz[v], (*lb) - sz[v], n - (*lb)});
        int mn = min({sz[v], (*lb) - sz[v], n - (*lb)});
        ans = min(ans, mx - mn);
    }

    auto it = non_anc.lower_bound((n - sz[v]) / 2);
    if (it != non_anc.end()){
        int mx = max({sz[v], (*it), n - (*it) - sz[v]});
        int mn = min({sz[v], (*it), n - (*it) - sz[v]});
        ans = min(ans, mx - mn);
    }
    if (it != non_anc.begin()){
        it--;
        int mx = max({sz[v], (*it), n - (*it) - sz[v]});
        int mn = min({sz[v], (*it), n - (*it) - sz[v]});
        ans = min(ans, mx - mn);
    }

    it = non_anc.lower_bound((n - sz[v]) / 2 + 1);
    if (it != non_anc.end()){
        int mx = max({sz[v], (*it), n - (*it) - sz[v]});
        int mn = min({sz[v], (*it), n - (*it) - sz[v]});
        ans = min(ans, mx - mn);
    }
    if (it != non_anc.begin()){
        it--;
        int mx = max({sz[v], (*it), n - (*it) - sz[v]});
        int mn = min({sz[v], (*it), n - (*it) - sz[v]});
        ans = min(ans, mx - mn);
    }

    anc.insert(sz[v]);
    for (int u : g[v]){
        if (u == p) continue;
        dfs(u, v);
    }
    anc.erase(sz[v]);
    non_anc.insert(sz[v]);
}

int main(){
    cin >> n;
    for (int i = 1; i < n; i ++){
        int u, v;
        cin >> u >> v;
        
        g[u].push_back(v);
        g[v].push_back(u);
    }

    pre_dfs(1);
    dfs(1);

    cout << ans << endl;
}

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