Submission #879791

#TimeUsernameProblemLanguageResultExecution timeMemory
879791TAhmed33Papričice (COCI20_papricice)C++98
110 / 110
128 ms26140 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize ("Ofast") const int MAXN = 2e5 + 25; const int bad = -1e7; inline int comb (int a, int b, int c) { return abs(2 * a - c) < abs(2 * b - c) ? a : b; } vector <int> adj[MAXN]; int sze[MAXN], n, in[MAXN], out[MAXN], t; int mn = 1e9; set <int> dfs (int pos, int par) { sze[pos] = 1; in[pos] = ++t; int mx = bad; set <int> cur; for (auto j : adj[pos]) { if (j == par) continue; auto x = dfs(j, pos); sze[pos] += sze[j]; if (cur.size() < x.size()) cur.swap(x); for (auto i : x) cur.insert(i); } auto tt = cur.lower_bound(sze[pos] / 2); if (tt != cur.end()) mx = *tt; if (tt != cur.begin()) { tt--; mx = comb(mx, *tt, sze[pos]); } cur.insert(sze[pos]); if (sze[pos] != 1 && pos != 1) mn = min(mn, max({n - sze[pos], sze[pos] - mx, mx}) - min({n - sze[pos], sze[pos] - mx, mx})); out[pos] = t; return cur; } set <int> x; void dfs2 (int pos, int par) { if (pos != 1 && !x.empty()) { auto t = x.lower_bound((n - sze[pos]) / 2); int ret = bad; if (t != x.end()) ret = *t; if (t != x.begin()) { t--; ret = comb(ret, *t, n - sze[pos]); } mn = min(mn, max({sze[pos], ret, n - sze[pos] - ret}) - min({sze[pos], ret, n - sze[pos] - ret})); } for (auto j : adj[pos]) if (j != par) dfs2(j, pos); x.insert(sze[pos]); } bool check (int x, int y) { return in[x] <= in[y] && in[y] <= out[x]; } int main () { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } dfs(1, -1); dfs2(1, -1); cout << mn << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...