Submission #1265120

#TimeUsernameProblemLanguageResultExecution timeMemory
1265120thaibeo123Race (IOI11_race)C++17
100 / 100
635 ms57788 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define pb push_back const int N = 1e6 + 5; int n, k, ans = 1e9; bool centroid[N]; int sz[N]; set<pair<int, int>> s; vector<pair<int, int>> g[N]; int dfs(int u, int par, int h) { sz[u] = 1; for (auto b : g[u]) { int v = b.fi; if (v != par && !centroid[v]) { sz[u] += dfs(v, u, h + 1); } } return sz[u]; } int find_centroid(int u, int par, int n) { for (auto b : g[u]) { int v = b.fi; if (v != par && !centroid[v] && sz[v] > n / 2) { return find_centroid(v, u, n); } } return u; } void count_path(int u, int par, int h, int e) { auto it = s.lower_bound({k - h, 0}); int cur = 0; if (it == s.end()) { cur = 1e9; } else { auto siu = *it; if (siu.fi != k - h) { cur = 1e9; } else { cur = siu.se; } } if (h <= k) { ans = min(ans, e + cur); } for (auto b : g[u]) { int v = b.fi, w = b.se; if (v != par && !centroid[v] && h + w <= k) { count_path(v, u, h + w, e + 1); } } } void update(int u, int par, int h, int e) { if (h <= k) { s.insert({h, e}); } for (auto b : g[u]) { int v = b.fi, w = b.se; if (v != par && !centroid[v] && h + w <= k) { update(v, u, h + w, e + 1); } } } void solve_centroid(int u) { int n = dfs(u, 0, 0); int c = find_centroid(u, 0, n); centroid[c] = 1; s.insert({0, 0}); for (auto b : g[c]) { int v = b.fi; int w = b.se; if (!centroid[v] && w <= k) { count_path(v, c, w, 1); update(v, c, w, 1); } } s.clear(); for (auto b : g[c]) { int v = b.fi; if (!centroid[v]) { solve_centroid(v); } } } int best_path(int a, int b, int H[][2], int L[]) { n = a, k = b; for (int i = 0; i < n - 1; ++i) { int u = H[i][0] + 1; int v = H[i][1] + 1; int w = L[i]; g[u].pb({v, w}); g[v].pb({u, w}); } solve_centroid(1); if (ans == 1e9) return -1; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...