Submission #342376

#TimeUsernameProblemLanguageResultExecution timeMemory
342376limabeansPapričice (COCI20_papricice)C++17
0 / 110
4 ms5248 KiB
#include <bits/stdc++.h> using namespace std; template<typename T> void out(T x) { cout << x << endl; exit(0); } #define watch(x) cout << (#x) << " is " << (x) << endl const int maxn = 2e5 + 10; const int LOG = 20; int n; vector<int> g[maxn]; int par[LOG+1][maxn]; int dep[maxn]; int siz[maxn]; void hack(int at, int p=0) { for (int i=1; i<LOG; i++) { par[i][at] = par[i-1][par[i-1][at]]; } siz[at] = 1; for (int to: g[at]) { if (to==p) continue; dep[to]=1+dep[at]; par[0][to]=at; hack(to, at); siz[at] += siz[to]; } } int lca(int u, int v) { if (dep[u] < dep[v]) swap(u,v); int dx = dep[u]-dep[v]; for (int i=0; i<LOG; i++) { if (dx>>i&1) { u = par[i][u]; } } if (u==v) return u; for (int j=LOG-1; j>=0; j--) { if (par[j][u]!=par[j][v]) { u = par[j][u]; v = par[j][v]; } } return par[0][u]; } int get(vector<int> a) { sort(a.begin(),a.end()); return a[2]-a[0]; } int lo; vector<int> vfind(multiset<int> &s, int x) { if (s.empty()) return {}; auto iter = s.lower_bound(x); if (iter == s.end()) --iter; vector<int> res; res.push_back(*iter); auto piter = iter; //fwd for (int it=0; it<2; it++) { ++iter; if (iter==s.end()) break; res.push_back(*iter); } iter = piter; //prv for (int it=0; it<2; it++) { if (iter==s.begin()) break; --iter; res.push_back(*iter); } return res; } multiset<int> A, B; vector<int> solveA(int x) { vector<int> res; auto tmp = vfind(A, (n+x)/2); res.insert(res.end(), tmp.begin(), tmp.end()); tmp = vfind(A, (n+x+1)/2); res.insert(res.end(), tmp.begin(), tmp.end()); tmp = vfind(A, n-x); res.insert(res.end(), tmp.begin(), tmp.end()); tmp = vfind(A, 2*x); res.insert(res.end(), tmp.begin(), tmp.end()); return res; } vector<int> solveB(int x) { vector<int> res; auto tmp = vfind(A, (n-x)/2); res.insert(res.end(), tmp.begin(), tmp.end()); tmp = vfind(A, (n-x+1)/2); res.insert(res.end(), tmp.begin(), tmp.end()); tmp = vfind(A, x); res.insert(res.end(), tmp.begin(), tmp.end()); tmp = vfind(A, n-2*x); res.insert(res.end(), tmp.begin(), tmp.end()); return res; } void dfs(int at, int p) { for (int ysiz: solveA(siz[at])) { int cur = get({siz[at], ysiz-siz[at], n-ysiz}); lo = min(lo, cur); } for (int ysiz: solveB(siz[at])) { int cur = get({siz[at], ysiz, n-siz[at]-ysiz}); lo = min(lo, cur); } A.insert(siz[at]); for (int to: g[at]) { if (to == p) continue; dfs(to, at); } A.erase(A.find(siz[at])); B.insert(siz[at]); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for (int i=0; i<n-1; i++) { int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } assert(n>=3); hack(1); lo = n; dfs(1,0); cout<<lo<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...