Submission #870613

#TimeUsernameProblemLanguageResultExecution timeMemory
870613epicci23Papričice (COCI20_papricice)C++17
15 / 110
3 ms6560 KiB
#include "bits/stdc++.h" using namespace std; #define pb push_back #define endl "\n" #define int long long #define sz(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() /* stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH * SIMPLIFY THE PROBLEM * READ THE STATEMENT CAREFULLY !!! if there is an specified/interesting smth(i.e. constraint) in the statement, then you must be careful about that */ const int N = 2e5; vector<int> v[N]; int dp[N]; void calc(int c,int p){ dp[c]=1; for(int x:v[c]){ if(x==p) continue; calc(x,c); dp[c]+=dp[x]; } } const int INF = 1e18; int ans = INF; multiset<int> ms; int n; void dfs(int c,int p){ ms.erase(ms.find(dp[c])); if(c!=1){ auto it = ms.lower_bound(dp[c]/2); if(it!=ms.end()){ int u = (*it); ans=min(ans,max({u,dp[c]-u,n-dp[c]}) - min({u,dp[c]-u,n-dp[c]})); } if(it!=ms.begin()){ it--; int u = (*it); ans=min(ans,max({u,dp[c]-u,n-dp[c]}) - min({u,dp[c]-u,n-dp[c]})); } it = ms.lower_bound((n-dp[c])/2); if(it!=ms.end()){ int u = (*it); ans=min(ans,max({u,dp[c],n-dp[c]-u}) - min({u,dp[c],n-dp[c]-u})); } if(it!=ms.begin()){ it--; int u = (*it); ans=min(ans,max({u,dp[c],n-dp[c]-u}) - min({u,dp[c],n-dp[c]-u})); } } for(int x:v[c]){ if(x==p) continue; dfs(x,c); } ms.insert(dp[c]); } void solve(){ cin >> n; for(int i=1;i<n;i++){ int a,b; cin >> a >> b; v[a].pb(b); v[b].pb(a); } calc(1,0); for(int i=1;i<=n;i++) ms.insert(dp[i]); dfs(1,0); cout << ans << endl; } int32_t main(){ cin.tie(0); ios::sync_with_stdio(0); int t=1;//cin >> t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...