Submission #1074569

#TimeUsernameProblemLanguageResultExecution timeMemory
1074569fryingducPapričice (COCI20_papricice)C++17
0 / 110
2 ms4956 KiB
#include "bits/stdc++.h" using namespace std; const int maxn = 2e5 + 5; int n; int sz[maxn]; vector<int> g[maxn]; int ans; void pre_dfs(int u, int prev) { sz[u] = 1; for(auto v:g[u]) { if(v == prev) continue; pre_dfs(v, u); sz[u] += sz[v]; } } multiset<int> a, b; int calc(int a, int b, int c) { return max({a, b, c}) - min({a, b, c}); } void dfs(int u, int prev) { for(auto v:g[u]) { if(v == prev) continue; a.insert(sz[u]); b.erase(b.find(sz[v])); dfs(v, u); a.erase(a.find(sz[u])); b.insert(sz[v]); auto it = a.lower_bound((n + sz[u]) / 2); if(it != a.end()) { int y = *it; ans = min(ans, calc(sz[u], y - sz[u], n - y)); } if(it != a.begin()) { --it; int y = *it; ans = min(ans, calc(sz[u], y - sz[u], n - y)); } it = b.lower_bound((n - sz[u]) / 2); if(it != b.end()) { int y = *it; ans = min(ans, calc(sz[u] - y, y, n - sz[u])); } if(it != b.begin()) { --it; int y = *it; ans = min(ans, calc(sz[u] - y, y, n - sz[u])); } } } void solve() { cin >> n; for(int i = 1; i < n; ++i) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } ans = n + 1; pre_dfs(1, 0); for(int i = 2; i <= n; ++i) { b.insert(sz[i]); } dfs(1, 0); cout << ans; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...