Submission #1210806

#TimeUsernameProblemLanguageResultExecution timeMemory
1210806395333emRace (IOI11_race)C++20
100 / 100
442 ms40124 KiB
#include <bits/stdc++.h> #define int long long #define emb emplace_back #define pii pair <int, int> using namespace std; const int N = 2e5 + 5; const int K = 1e6 + 5; const int inf = 1e18; int n, k, ans = inf, sz[N], cal[K]; vector <pii> adj[N], temp; bool del[N]; void dfssz(int u, int p){ sz[u] = 1; for (auto [w, v] : adj[u]) { if (v == p || del[v]) continue; dfssz(v, u); sz[u] += sz[v]; } } int centroid(int u, int p, int siz){ for (auto [w, v] : adj[u]) { if (v == p || del[v]) continue; if (2 * sz[v] > siz) return centroid(v, u, siz); } return u; } void dfs(int u, int p, int dis, int cnt){ temp.emb(dis, cnt); if (k >= dis && cal[k - dis] != inf) ans = min(ans, cnt + cal[k - dis]); for (auto [w, v] : adj[u]) { if (v == p || del[v]) continue; dfs(v, u, dis + w, cnt + 1); } } void dfsdel(int u, int p, int dis){ if (dis <= k) cal[dis] = inf; for (auto [w, v] : adj[u]) { if (v == p || del[v]) continue; dfsdel(v, u, dis + w); } } void decompose(int u){ dfssz(u, u); u = centroid(u, u, sz[u]); del[u] = true; cal[0] = 0; for (auto [w, v] : adj[u]) { if (del[v]) continue; temp.clear(); dfs(v, u, w, 1); for (auto [dis, cnt] : temp) { if (dis <= k) cal[dis] = min(cal[dis], cnt); } } for (auto [w, v] : adj[u]) { if (del[v]) continue; dfsdel(v, u, w); } for (auto [w, v] : adj[u]) { if (!del[v]) decompose(v); } } int32_t best_path(int32_t nn, int32_t kk, int32_t edge[][2], int32_t wei[]){ n = nn, k = kk; for (int i = 0; i <= k; i++) cal[i] = inf; for (int i = 0; i < n - 1; i++) { auto v = edge[i]; adj[v[0]].emb(wei[i], v[1]); adj[v[1]].emb(wei[i], v[0]); } decompose(0); return (ans == inf ? -1 : 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...