oj.uz

Submission #439079

# Submission time Handle Problem Language Result Execution time Memory
439079 2021-06-29T07:37:08 Z 2548631 Papričice (COCI20_papricice) C++17
0 / 110
 5 ms 4940 KB 
#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(next(it)!=sA.end()) upd(cnt[u],n-*next(it),*next(it)-cnt[u]);
        if(it!=sA.begin()) upd(cnt[u],n-*prev(it),*prev(it)-cnt[u]);
    }
    it=sB.upper_bound((n-cnt[u])/2);
    if(it!=sB.end()) {
        upd(cnt[u],n-*it-cnt[u],*it);
        //if(next(it)!=sB.end()) upd(cnt[u],n-*next(it)-cnt[u],*next(it));
        if(it!=sB.begin()) upd(cnt[u],n-*prev(it)-cnt[u],*prev(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(sA.find(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;
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Incorrect 4 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Incorrect 4 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Incorrect 4 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -