Submission #881063

#TimeUsernameProblemLanguageResultExecution timeMemory
881063Cyber_WolfPapričice (COCI20_papricice)C++17
110 / 110
288 ms41296 KiB
#include <bits/stdc++.h> using namespace std; #define lg long long #define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); const lg N = 5e5+5; vector<lg> adj[N], late; lg sz[N], ans = N, n; multiset<lg> se1, se2; void dfs(lg src, lg par = -1) { sz[src] = 1; for(auto it : adj[src]) { if(it == par) continue; dfs(it, src); sz[src] += sz[it]; } return; } lg cost(lg a, lg b, lg c) { return max({abs(a-b), abs(a-c), abs(b-c)}); } void dfs2(lg src, lg par = -1) { se1.insert(sz[src]); auto it = se1.lower_bound(n/2+sz[src]/2); lg z = n; if(it != se1.end()) { z = (*it); } if(it != se1.begin()) { it--; if(cost(sz[src], n-(*it), (*it)-sz[src]) <= cost(sz[src], n-z, z-sz[src])) { z = (*it); } } ans = min(ans, cost(sz[src], n-z, z-sz[src])); it = se2.lower_bound((n-sz[src])/2); z = n; if(it != se2.end()) { z = (*it); } if(it != se2.begin()) { it--; if(cost(sz[src], n-sz[src]-(*it), (*it)) <= cost(sz[src], n-z-sz[src], z)) { z = (*it); } } ans = min(ans, cost(sz[src], z, n-z-sz[src])); for(auto it : adj[src]) { if(it == par) continue; while(late.size()) { se2.insert(late.back()); late.pop_back(); } dfs2(it, src); } se1.erase(se1.find(sz[src])); late.push_back(sz[src]); return; } int main() { fastio; cin >> n; for(int i = 1; i < n; i++) { lg u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } dfs(1); dfs2(1); late.clear(); se2.clear(); se1.clear(); for(int i = 1; i <= n; i++) reverse(adj[i].begin(), adj[i].end()); dfs2(1); cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...