Submission #1016154

#TimeUsernameProblemLanguageResultExecution timeMemory
1016154vjudge1Papričice (COCI20_papricice)C++17
0 / 110
3 ms5720 KiB
#include <bits/stdc++.h> using namespace std; const int M = 2e5 + 1; vector<int> nei[M]; int subt[M],ans,n; set<int> se,se1; void calc(int u,int p=0) { subt[u]=1; for (int i:nei[u]) if (i!=p) { calc(i,u); subt[u]+=subt[i]; } } void dfs(int u,int p=0) { int x=subt[u]+(n-subt[u])/2; auto it=se.upper_bound(x); int val=-1; if (it!=se.end()) val=*it; if (it!=se.begin()) { it--; if (val==-1 || val-x>x-*it) val=*it; } if (val!=-1) ans=min(max(max(abs(val-subt[u]*2),abs(n-val-subt[u])),abs(n-2*val+subt[u])),ans); se.insert(subt[u]); x=(n-subt[u])/2; it=se1.upper_bound(x); val=-1; if (it!=se1.end()) val=*it; if (it!=se1.begin()) { it--; if (val==-1 || val-x>x-*it) val=*it; } if (val!=-1) ans=min(ans,max(abs(n-2*val),max(abs(n-val-subt[u]),abs(val-subt[u])))); for (int i:nei[u]) if (i!=p) dfs(i,u); se.erase(subt[u]); se1.insert(subt[u]); } int main() { cin>>n; ans=n; for (int i=1;i<n;i++) { int u,v; cin>>u>>v; nei[u].push_back(v); nei[v].push_back(u); } calc(1); dfs(1); cout<<ans<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...