Submission #439132

#	Time	Username	Problem	Language	Result	Execution time	Memory
439132		2548631	Papričice (COCI20_papricice)	C++17	110 / 110	324 ms	21664 KiB

papricice

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> cp;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vii;
typedef vector<cp> vcp;
typedef vector<ld> vld;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vii> vvii;

#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define forw(i,l,r) for( int i = (l) ; i < (r) ; i++ )
#define forb(i,r,l) for( int i = (r) ; i >= (l) ; i-- )
#define log2i(x) (64 - __builtin_clzll(1ll*(x)) - 1)
#define numBit(x) (__builtin_popcountll(1ll*(x)))
#define getBit(x,i) ((x)>>(i)&1)
#define Pi acos(-1.0l)
#define sz(x) int(x.size())
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define debug(x) cerr << #x << " = " << x << '\n';

const int N = 2e5+7;
int n,ans=N;
int cnt[N];
vi edge[N];
set<int> sA,sB;

void pre_dfs(int u, int par=-1) {
    cnt[u]=1;
    for(auto v:edge[u]) if(v!=par) {
        pre_dfs(v,u);
        cnt[u]+=cnt[v];
    }
}

void upd(int x, int y, int z) {
    ans=min(ans,max({x,y,z})-min({x,y,z}));
}

void process(int u) {
    auto it=sA.upper_bound((n+cnt[u])/2);
    if(it!=sA.end()) upd(cnt[u],n-*it,*it-cnt[u]);
    if(it!=sA.begin()) {
        it--;
        upd(cnt[u],n-*it,*it-cnt[u]);
    }
    it=sB.upper_bound((n-cnt[u])/2);
    if(it!=sB.end()) upd(cnt[u],n-*it-cnt[u],*it);
    if(it!=sB.begin()) {
        it--;
        upd(cnt[u],n-*it-cnt[u],*it);
    }
}

void dfs(int u, int par=-1) {
    process(u);
    sA.insert(cnt[u]);
    for(auto v:edge[u]) if(v!=par) dfs(v,u);
    sA.erase(cnt[u]);
    sB.insert(cnt[u]);
}

int main() {
    fastIO;
#ifndef ONLINE_JUDGE
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
#endif // ONLINE_JUDGE

    cin >> n;
    forw(i,1,n) {
        int u,v; cin >> u >> v;
        u--, v--;
        edge[u].pb(v);
        edge[v].pb(u);
    }
    pre_dfs(0);
    dfs(0);
    cout << ans << '\n';
    return 0;
}

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