Submission #464419

#	Time	Username	Problem	Language	Result	Execution time	Memory
464419		dannyboy20031204	Papričice (COCI20_papricice)	C++17	110 / 110	290 ms	26124 KiB

papricice

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define double long double
using namespace std;
void db() {cerr << endl;}
template <typename T, typename ...U> void db(T a, U ...b) {
    cerr << a << ' ', db(b...);
}
const int N = 2e5 + 1, inf = 1e9 + 1;
int n, ans = inf;
vector<int> g[N];
int sz[N];
multiset<int> s, s2;
void dfs1(int u, int p){
    sz[u] = 1;
    for (int i : g[u]){
        if (i == p)
            continue;
        dfs1(i, u);
        sz[u] += sz[i];
    }
    //db(u, sz[u]);
}
int f(int a, int b, int c){
    return max({abs(a - b), abs(a - c), abs(b - c)});
}
void dfs(int u, int p){
    auto it = s2.lower_bound((n + sz[u]) / 2);
    if (it != s2.end())
        ans = min(ans, f(sz[u], *it - sz[u], n - *it));
    if (it != s2.begin()){
        --it;
        ans = min(ans, f(sz[u], *it - sz[u], n - *it));
    }

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

    s2.insert(sz[u]);
    for (int i : g[u]){
        if (i == p)
            continue;
        dfs(i, u);
    }
    s.insert(sz[u]);
    s2.erase(s2.lower_bound(sz[u]));
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1, -1);
    dfs(1, -1);
    cout << ans << '\n';
}

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