Submission #439071

#TimeUsernameProblemLanguageResultExecution timeMemory
4390712548631Papričice (COCI20_papricice)C++17
0 / 110
5 ms5020 KiB
#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.lower_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.lower_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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...