Submission #1016157

#TimeUsernameProblemLanguageResultExecution timeMemory
1016157vjudge1Papričice (COCI20_papricice)C++17
0 / 110
2 ms4956 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int n, sz[N], ans = 1e9; vector<int> g[N]; void pre_dfs(int v, int p = -1){ sz[v] = 1; for (int u : g[v]){ if (u == p) continue; pre_dfs(u, v); sz[v] += sz[u]; } } set<int> anc, non_anc; void dfs(int v, int p = -1){ auto lb = anc.lower_bound((n - sz[v]) / 2); if (lb != anc.end()){ int mx = max({sz[v], (*lb) - sz[v], n - (*lb)}); int mn = min({sz[v], (*lb) - sz[v], n - (*lb)}); ans = min(ans, mx - mn); } if (lb != anc.begin()){ lb--; int mx = max({sz[v], (*lb) - sz[v], n - (*lb)}); int mn = min({sz[v], (*lb) - sz[v], n - (*lb)}); ans = min(ans, mx - mn); } lb = anc.lower_bound((n - sz[v]) / 2 + 1); if (lb != anc.end()){ int mx = max({sz[v], (*lb) - sz[v], n - (*lb)}); int mn = min({sz[v], (*lb) - sz[v], n - (*lb)}); ans = min(ans, mx - mn); } if (lb != anc.begin()){ lb--; int mx = max({sz[v], (*lb) - sz[v], n - (*lb)}); int mn = min({sz[v], (*lb) - sz[v], n - (*lb)}); ans = min(ans, mx - mn); } auto it = non_anc.lower_bound((n - sz[v]) / 2); if (it != non_anc.end()){ int mx = max({sz[v], (*it) - sz[v], n - (*it)}); int mn = min({sz[v], (*it) - sz[v], n - (*it)}); ans = min(ans, mx - mn); } if (it != non_anc.begin()){ it--; int mx = max({sz[v], (*it) - sz[v], n - (*it)}); int mn = min({sz[v], (*it) - sz[v], n - (*it)}); ans = min(ans, mx - mn); } it = non_anc.lower_bound((n - sz[v]) / 2 + 1); if (it != non_anc.end()){ int mx = max({sz[v], (*it) - sz[v], n - (*it)}); int mn = min({sz[v], (*it) - sz[v], n - (*it)}); ans = min(ans, mx - mn); } if (it != non_anc.begin()){ it--; int mx = max({sz[v], (*it) - sz[v], n - (*it)}); int mn = min({sz[v], (*it) - sz[v], n - (*it)}); ans = min(ans, mx - mn); } anc.insert(sz[v]); for (int u : g[v]){ if (u == p) continue; dfs(u, v); } anc.erase(sz[v]); non_anc.insert(sz[v]); } int main(){ 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); } pre_dfs(1); dfs(1); cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...