Submission #1248337

#TimeUsernameProblemLanguageResultExecution timeMemory
1248337dfhdfhdsfPapričice (COCI20_papricice)C++20
0 / 110
7 ms9792 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 200000 + 5; int n; vector<int> g[MAXN]; int sub[MAXN], heavy[MAXN], parent_[MAXN]; int tin[MAXN], tout[MAXN], euler_[MAXN], timer_ = 0; long long answer = LLONG_MAX; /* --------- 1st DFS : size, heavy child, euler order --------- */ void dfs_sz(int u, int p = 0) { parent_[u] = p; sub[u] = 1; int mx = 0; tin[u] = ++timer_; euler_[timer_] = u; for (int v : g[u]) if (v != p) { dfs_sz(v, u); sub[u] += sub[v]; if (sub[v] > mx) mx = sub[v], heavy[u] = v; } tout[u] = timer_; } /* multiset chứa kích thước các cây con hiện tại */ /* cnt[x] – số lần x xuất hiện (hỗ trợ remove nhanh) */ multiset<int> S; vector<int> bucket[MAXN]; // bucket[id] = list size trong subtree id void add_subtree(int u) { // đi qua euler để lấy toàn bộ cạnh khác gốc trong cây con u for (int t = tin[u]; t <= tout[u]; ++t) { int v = euler_[t]; if (v == 1) continue; // đỉnh gốc không có cạnh đi lên S.insert(sub[v]); bucket[u].push_back(sub[v]); } } void remove_subtree(int u) { for (int x : bucket[u]) S.erase(S.find(x)); } /* tìm giá trị trong multiset S gần nhất với target */ inline void try_update(long long A, long long B, long long t) { long long x,y,z, diff; /* 2 công thức */ /* 1. nested : t , A-t , B */ x = t; y = A - t; z = B; diff = max({x,y,z}) - min({x,y,z}); answer = min(answer, diff); /* 2. disjoint: A , t , B-t (chỉ hợp lệ khi B>t , nhưng nếu B==t hoặc B<t chênh lệch càng lớn → không thể nhỏ hơn lời giải hiện tại nên không cần ràng buộc) */ x = A; y = t; z = B - t; if (z>0) { diff = max({x,y,z}) - min({x,y,z}); answer = min(answer, diff); } } void query(multiset<int> &M, long long target, long long A, long long B) { if (M.empty()) return; auto it = M.lower_bound((int)target); if (it != M.end()) try_update(A,B,*it); if (it != M.begin()) try_update(A,B,*prev(it)); } /* --------- 2nd DFS : DSU on tree ----------------------------- */ void dfs_dsu(int u, bool keep) { /* process light children first */ for (int v : g[u]) if (v != parent_[u] && v != heavy[u]) dfs_dsu(v, false); /* heavy child with keep = true */ if (heavy[u]) dfs_dsu(heavy[u], true); /* add every light child’s subtree into S */ for (int v : g[u]) if (v != parent_[u] && v != heavy[u]) { add_subtree(v); } /* add current node’s own edge (if not root) */ if (u != 1) { S.insert(sub[u]); } /* ------------ TÍNH KẾT QUẢ ---------------- */ if (u != 1) // chỉ các cạnh khác rễ mới cắt được { long long A = sub[u]; long long B = n - A; /* 1. cạnh thứ hai bên TRONG cây con u */ // mọi kích thước trong subtree u ngoại trừ sub[u] chính là // bucket[u] + mọi bucket[light child] + bucket[heavy child] (đã ở S) // để có "inside", ta chỉ cần nhìn vào S rồi xoá phần Outside // --> dùng riêng multiset insideSub (đã được build ở bước add) : multiset<int> inside; for (int v : g[u]) if (v != parent_[u]) inside.insert(sub[v]); // cạnh ngay dưới u if (!inside.empty()) { long long tgt = A / 2; query(inside, tgt, A, B); } /* 2. cạnh thứ hai nằm bên NGOÀI cây con u => chính là multiset S sau khi ta đã add toàn bộ subtree u ngoại trừ sub[u] đã ở trong S. */ long long tgt2 = B / 2; multiset<int> outside = S; // loại bỏ toàn bộ subtree u (đã add ở thân hàm) để lại phần ngoài remove_subtree(u); if (u != 1) outside.erase(outside.find(sub[u])); query(outside, tgt2, A, B); add_subtree(u); // khôi phục } /* ---------------------------------------------------------- */ if (!keep) { remove_subtree(u); if (u != 1) S.erase(S.find(sub[u])); } } /* ============================================================= */ int main() { ios::sync_with_stdio(false); cin.tie(nullptr); if (!(cin >> n)) return 0; for (int i = 1; i < n; ++i) { int x,y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } dfs_sz(1); add_subtree(1); // đưa toàn bộ cạnh vào multiset S dfs_dsu(1, true); cout << answer << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...