Submission #484925

#	Time	Username	Problem	Language	Result	Execution time	Memory
484925		Kirill22	Papričice (COCI20_papricice)	C++17	110 / 110	271 ms	30072 KiB

papricice

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int) (x).size()

const int N = 200000;
int n, ans = (int) 1e9;
vector<int> g[N];
int cnt[N];
multiset<int> a, b;

void get_sz(int v, int pr) {
    cnt[v] = 1;
    for (auto x : g[v]) {
        if (x != pr) {
            get_sz(x, v);
            cnt[v] += cnt[x];
        }
    }
}

void solve(int v, int pr = -1) {
    {
        int X = n - cnt[v];
        auto it = b.lower_bound(X / 2);
        if (it != b.end()) {
            ans = min(ans, max({cnt[v], *it, X - *it}) - min({cnt[v], *it, X - *it}));
        }
        if (it != b.begin()) {
            it--;
            ans = min(ans, max({cnt[v], *it, X - *it}) - min({cnt[v], *it, X - *it}));
        }
    }
    {
        int X = n + cnt[v];
        auto it = a.lower_bound(X / 2);
        if (it != a.end()) {
            ans = min(ans, max({cnt[v], *it - cnt[v], n - *it}) - min({cnt[v], *it - cnt[v], n - *it}));
        }
        if (it != a.begin()) {
            it--;
            ans = min(ans, max({cnt[v], *it - cnt[v], n - *it}) - min({cnt[v], *it - cnt[v], n - *it}));
        }
    }
    a.insert(cnt[v]);
    for (auto x : g[v]) {
        if (x != pr) {
            solve(x, v);
        }
    }
    a.erase(a.find(cnt[v]));
    b.insert(cnt[v]);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    get_sz(0, -1);
    solve(0, -1);
    cout << ans;
}

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