Submission #1248332

#TimeUsernameProblemLanguageResultExecution timeMemory
1248332dfhdfhdsfPapričice (COCI20_papricice)C++20
15 / 110
2 ms840 KiB
#include <bits/stdc++.h> using namespace std; using vi = vector<int>; const int INF = 1e9; int n; vector<vi> adj, children; vi tin, tout, euler, sz, B; int timer; int ans; // --- 1) DFS1: Euler tour + tính sz[u] --- void dfs1(int u, int p){ tin[u] = ++timer; euler[timer] = u; sz[u] = 1; for(int v: adj[u]){ if(v == p) continue; children[u].push_back(v); dfs1(v, u); sz[u] += sz[v]; } tout[u] = timer; } // bests[u] sẽ chứa 1–2 ứng viên a' cho case disjoint của u vector<vector<int>> bests; // --- 2) Forward scan cho prefix [1..tin[u]-1], loại trừ root --- void forward_scan(){ multiset<int> st; vector<vector<int>> atTin(n+1); for(int u = 2; u <= n; u++) atTin[tin[u]].push_back(u); for(int i = 1; i <= n; i++){ // xử lý disjoint-prefix cho mọi u với tin[u] == i for(int u: atTin[i]){ int r = n - sz[u]; int target = r / 2; if(!st.empty()){ auto it = st.lower_bound(target); if(it != st.end()) bests[u].push_back(*it); if(it != st.begin()){ --it; bests[u].push_back(*it); } } } // chèn B[i] = sz[euler[i]] nếu euler[i] != 1 if(euler[i] != 1) st.insert(B[i]); } } // --- 3) Backward scan cho suffix [tout[u]+1..n], loại trừ root --- void backward_scan(){ multiset<int> st; vector<vector<int>> atTout(n+2); for(int u = 2; u <= n; u++) atTout[tout[u]].push_back(u); for(int i = n; i >= 1; i--){ for(int u: atTout[i]){ int r = n - sz[u]; int target = r / 2; if(!st.empty()){ auto it = st.lower_bound(target); if(it != st.end()) bests[u].push_back(*it); if(it != st.begin()){ --it; bests[u].push_back(*it); } } } if(euler[i] != 1) st.insert(B[i]); } } // --- 4) DSU-on-Tree để tìm case nested và kết hợp disjoint từ bests[u] --- set<int>* dfs_dsu(int u){ // S chứa sz[x] cho tất cả x trong subtree(u), x != u auto *S = new set<int>(); for(int v: children[u]){ auto *Sv = dfs_dsu(v); if(S->size() < Sv->size()) swap(S, Sv); // merge Sv vào S for(int x: *Sv) S->insert(x); delete Sv; } // --- case nested: tìm a trong S sao cho a ≈ sz[u]/2 --- if(!S->empty()){ int s = sz[u], r = n - s; int target = s / 2; auto it = S->lower_bound(target); vector<int> cands; if(it != S->end()) cands.push_back(*it); if(it != S->begin()){ --it; cands.push_back(*it); } for(int a: cands){ int b = s - a; int mx = max({a,b,r}); int mn = min({a,b,r}); ans = min(ans, mx - mn); } } // --- case disjoint: dùng bests[u] từ forward/backward --- int s = sz[u]; for(int a: bests[u]){ int b = (n - s) - a; int c = s; int mx = max({a,b,c}); int mn = min({a,b,c}); ans = min(ans, mx - mn); } // thêm sz[u] vào S để các ancestor có thể dùng S->insert(sz[u]); return S; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; adj.assign(n+1, {}); children.assign(n+1, {}); tin.assign(n+1,0); tout.assign(n+1,0); euler.assign(n+1,0); sz.assign(n+1,0); B.assign(n+1,0); bests.assign(n+1, {}); for(int i = 1, x, y; i < n; i++){ cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } timer = 0; dfs1(1, 0); // xây B[i] = sz[euler[i]] for(int i = 1; i <= n; i++) B[i] = sz[euler[i]]; // thu disjoint‑candidates forward_scan(); backward_scan(); ans = INF; // DSU‑on‑Tree tổng hợp nested & disjoint auto *rootSet = dfs_dsu(1); delete rootSet; cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...