Submission #677331

#	Time	Username	Problem	Language	Result	Execution time	Memory
677331		rafatoa	Papričice (COCI20_papricice)	C++17	110 / 110	226 ms	27696 KiB

papricice

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

#define F first
#define S second
#define int long long
const int INF = 1e18;

void solve(){
    int n; cin >> n;
    vector<vector<int>> adj(n+1);

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

    vector<int> sub(n+1);
    map<int, int> a, b;
    function<void(int, int)> dfs0 = [&](int s, int e){
        sub[s] = 1;
        for(auto &u:adj[s]){
            if(u == e) continue;
            dfs0(u, s);
            sub[s] += sub[u];
        }
    };
    dfs0(1, 0);

    int ans = INF;
    function<void(int, int)> dfs = [&](int s, int e){
        auto it1 = a.lower_bound((n+sub[s])/2);
        auto it2 = b.lower_bound((n-sub[s])/2);

        if(!a.empty()){
            if(it1 != a.end()) ans = min(ans, max({sub[s], it1->F-sub[s], n-it1->F}) - min({sub[s], it1->F-sub[s], n-it1->F}));
            if(it1 != a.begin()) it1--, ans = min(ans, max({sub[s], it1->F-sub[s], n-it1->F}) - min({sub[s], it1->F-sub[s], n-it1->F}));
        }
        if(!b.empty()){
            if(it2 != b.end()) ans = min(ans, max({sub[s], it2->F, n-it2->F-sub[s]}) - min({sub[s], it2->F, n-it2->F-sub[s]}));
            if(!b.empty() && it2 != b.begin()) it2--, ans = min(ans, max({sub[s], it2->F, n-it2->F-sub[s]}) - min({sub[s], it2->F, n-it2->F-sub[s]}));
        }

        a[sub[s]]++;
        for(auto &u:adj[s]){
            if(u == e) continue;
            dfs(u, s);
        }
        a[sub[s]]--;
        if(a[sub[s]] == 0) a.erase(sub[s]);
        b[sub[s]]++;
    };
    dfs(1, 0);
    cout << ans << "\n";
}

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

    solve();
    return 0;
}

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