제출 #1176436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176436		nguyenkhangninh99	Papričice (COCI20_papricice)	C++20	110 / 110	169 ms	39032 KiB

papricice

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

const int maxn = 2e5 + 5;
vector<int> g[maxn];
int sz[maxn];
set<int> s[maxn];
int n, ans = 1e9;

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

void dfs(int u, int p){
    for(int v: g[u]){
        if (v == p) continue;
        dfs(v, u);
        if (s[u].size() < s[v].size()) swap(s[u], s[v]);
        for(int x: s[v]) {
            auto it = s[u].lower_bound((n - x) / 2);
            if(it != s[u].end()) ans = min(ans, max({*it, n - *it - x, x}) - min({*it, n - *it - x, x}));
            --it;
            if(it != s[u].begin()) ans = min(ans, max({*it, n - *it - x, x}) - min({*it, n - *it - x, x}));
        }
        for(int x: s[v]) s[u].insert(x); 
    }

    if (!s[u].empty()){
        auto it = s[u].lower_bound(sz[u] / 2);
        if(it != s[u].end()) ans = min(ans, max({*it, sz[u] - *it, n - sz[u]}) - min({*it, sz[u] - *it, n - sz[u]}));
        --it;
        if(it != s[u].begin()) ans = min(ans, max({*it, sz[u] - *it, n - sz[u]}) - min({*it, sz[u] - *it, n - sz[u]}));
    }

    s[u].insert(sz[u]);
}

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

    dfssz(1, 0);
    dfs(1, 0);
    cout << ans;
}

signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);

    solve();
}

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