Submission #1265117

#TimeUsernameProblemLanguageResultExecution timeMemory
1265117thaibeo123Race (IOI11_race)C++17
0 / 100
11 ms23872 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, mx, ans = 1e9; bool centroid[N]; int dp[N], sz[N]; vector<pair<int, int>> g[N]; int dfs(int u, int par, int h) { sz[u] = 1; mx = max(mx, h); 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) { if (h <= k) { ans = min(ans, e + dp[k - h]); } //cout << u << " " << h << " " << e << " " << k - h << " " << dp[k - h] << "\n"; 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) { dp[h] = min(dp[h], e); } 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 solve_centroid(int u) { mx = 0; int n = dfs(u, 0, 0); int c = find_centroid(u, 0, n); centroid[c] = 1; for (int i = 1; i <= min(k, mx * 10); ++i) { dp[i] = 1e9; } dp[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); } } for (auto b : g[c]) { int v = b.fi; if (!centroid[v]) { solve_centroid(v); } } } int best_path(int N, int K, int H[][2], int L[]) { n = N, k = K; 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...