Submission #494990

#TimeUsernameProblemLanguageResultExecution timeMemory
494990VictorPapričice (COCI20_papricice)C++17
15 / 110
10 ms14508 KiB
// #pragma GCC target ("avx,avx2,fma") // #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast // #pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define per(i, a, b) for (int i = (b - 1); i >= (a); --i) #define trav(a, x) for (auto &a : x) #define all(x) x.begin(), x.end() #define sz(x) x.size() #define pb push_back #define debug(x) cout << #x << " = " << x << endl #define umap unordered_map #define uset unordered_set typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; const int INF = 1'000'000'007; int n, ans = INF, sub_size[200001], root; set<int> nodes[200001]; vi graph[200001]; void dfs(int u, int p) { sub_size[u] = 1; trav(v, graph[u]) if (v != p) { dfs(v, u); sub_size[u] += sub_size[v]; if (sz(nodes[u]) < sz(nodes[v])) nodes[u].swap(nodes[v]); trav(val, nodes[v]) nodes[u].insert(val); nodes[v].clear(); } trav(v, graph[u]) if (v != p) nodes[u].insert(sub_size[v]); if (u != root && sub_size[u] != 1) { int above = n - sub_size[u]; auto it=nodes[u].lower_bound(sub_size[u] / 2); if(it==nodes[u].end())--it; int p1 = *it, p2 = sub_size[u] - p1; int mx = max(above, max(p1, p2)), mn = min(above, min(p1, p2)); ans = min(ans, mx - mn); } } int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); cin >> n; rep(i, 1, n) { int u, v; cin >> u >> v; graph[--u].pb(--v); graph[v].pb(u); } rep(i,0,10) { root = rand()%n; dfs(root, root); nodes[root].clear(); } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...