Submission #334054

#	Time	Username	Problem	Language	Result	Execution time	Memory
334054		wiwiho	Papričice (COCI20_papricice)	C++14	110 / 110	331 ms	29420 KiB

papricice

#include <bits/stdc++.h>

#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define eb emplace_back
#define printv(a, b) { \
    bool ps = false; \
    for(auto v : a){ \
        if(ps) b << " "; \
        b << v; ps = true; \
    } \
    b << "\n"; \
}
#define lsort(a) sort(iter(a))

using namespace std;

typedef long long ll;

const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

vector<vector<int>> g;
multiset<int> s1, s2;
vector<int> sz;
int ans = MAX;
int n;

void dfs(int now, int p){
    for(int i : g[now]){
        if(i == p) continue;
        dfs(i, now);
        sz[now] += sz[i];
    }
}

int diff(int a, int b, int c){
    return max({abs(a - b), abs(b - c), abs(a - c)});
}

void dfs2(int now, int p){
    int t = sz[now];
    auto it = s1.lower_bound((n - t) / 2);
    if(it != s1.end()) ans = min(ans, diff(t, *it, n - t - *it));
    if(it != s1.begin()) it--, ans = min(ans, diff(t, *it, n - t - *it));
    it = s2.lower_bound(t + (n - t) / 2);
    if(it != s2.end()) ans = min(ans, diff(t, *it - t, n - *it));
    if(it != s2.begin()) it--, ans = min(ans, diff(t, *it - t, n - *it));

    s2.insert(sz[now]);
    for(int i : g[now]){
        if(i != p) dfs2(i, now);
    }

    s2.erase(s2.find(sz[now]));
    s1.insert(sz[now]);
}

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

    cin >> n;
    g.resize(n + 1);
    sz.resize(n + 1, 1);

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

    dfs(1, 1);
    dfs2(1, 1);

    cout << ans << "\n";
    
    return 0;
}

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