Submission #331556

#TimeUsernameProblemLanguageResultExecution timeMemory
331556nekiPapričice (COCI20_papricice)C++14
50 / 110
14 ms14700 KiB
#include <bits/stdc++.h> #define loop(i, a, b) for(long long i=a;i<b;i++) #define pool(i, a, b) for(long long i=a-1;i>=b;i--) #define fore(i, a) for(auto&& i:a) #define fi first #define se second #define ps(a) push_back(a) #define pb(a) pop_back(a) #define sc scanf #define vc vector #define pa pair<ll, ll> #define ll long long #define lb lower_bound #define ub upper_bound #define all(a) a.begin(), a.end() #define llmax LLONG_MAX/2 #define llmin -LLONG_MAX/2 using namespace std; #define mn 100100 #define pa pair<ll, ll> #define ld long double vc<ll> edg[mn]; ll n, siz[mn]; void get(ll u, ll p){ siz[u]=1; fore(v, edg[u]) if(v!=p){ get(v, u); siz[u]+=siz[v]; } } set<ll> alls, sub[mn]; ll raz(ll a, ll b, ll c){return max(a, max(b, c)) - min(a, min(b, c));} ll ans; void dfs(ll u, ll p){ auto z=alls.lower_bound((n-siz[u])/2); if(z!=alls.end()) ans=min(ans, raz(siz[u], (*z), n-(*z)-siz[u])); if(z!=alls.begin()){--z; ans=min(ans, raz(siz[u], (*z), n-(*z)-siz[u]));} fore(v, edg[u]) if(v!=p){ dfs(v, u); if(sub[v].size()>sub[u].size()) swap(sub[v], sub[u]); } fore(v, edg[u]) if(v!=p){ fore(el, sub[v]) sub[u].insert(el); } auto s=sub[u].lower_bound(siz[u]/2); /*if(s!=sub[u].end()){ cout << n << " "<<siz[u]<< " "<<(*s)<<endl; cout<<n-siz[u]<<" " <<siz[u] -(*s)<<" "<< (*s)<< " "<<raz(n-siz[u], siz[u] -(*s), (*s))<<endl; }*/ if(s!=sub[u].end()) ans=min(ans, raz(n-siz[u], siz[u] -(*s), (*s))); if(s!=sub[u].begin()){--s; ans=min(ans, raz(n-siz[u], siz[u] -(*s), (*s)));} sub[u].insert(siz[u]); alls.insert(siz[u]); } int main() { cin >> n; ans=raz(1, 1, n-2); loop(i, 0, n-1){ ll a, b;cin >> a >> b; edg[a].ps(b); edg[b].ps(a); } get(1, -1); dfs(1, -1); cout << ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...