제출 #693196

#제출 시각아이디문제언어결과실행 시간메모리
693196leeh18경주 (Race) (IOI11_race)C++17
43 / 100
3069 ms22712 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; int best_path(int N, int K, int H[][2], int L[]) { vector<vector<pair<int, int>>> adj(N); for (auto i = 0; i < N - 1; ++i) { auto u = H[i][0]; auto v = H[i][1]; adj[u].emplace_back(v, L[i]); adj[v].emplace_back(u, L[i]); } constexpr auto inf = numeric_limits<int>::max() / 2; vector<int> subtree_size(N), r(K + 1, inf); vector<bool> done(N); r[0] = 0; auto ans = inf; auto dfs_size = [&](auto self, int u, int p) -> int { auto &ret = subtree_size[u]; ret = 1; for (auto [v, w] : adj[u]) { if (v != p && !done[v]) { ret += self(self, v, u); } } return ret; }; auto dfs_centroid = [&](auto self, int u, int p, int sz) -> int { for (auto [v, w] : adj[u]) { if (v != p && !done[v] && sz / 2 < subtree_size[v]) { return self(self, v, u, sz); } } return u; }; auto dfs = [&](auto self, int u, int p, int d, int cnt, auto f) -> void { if (K < d) { return; } f(d, cnt); for (auto [v, w] : adj[u]) { if (v != p && !done[v]) { self(self, v, u, d + w, cnt + 1, f); } } }; auto centroid_decomposition = [&](auto self, int u) -> void { auto sz = dfs_size(dfs_size, u, u); u = dfs_centroid(dfs_centroid, u, u, sz); done[u] = true; for (auto [v, w] : adj[u]) { dfs(dfs, v, u, w, 1, [&](int d, int cnt) { ans = min(ans, r[K - d] + cnt); }); dfs(dfs, v, u, w, 1, [&](int d, int cnt) { r[d] = min(r[d], cnt); }); } for (auto [v, w] : adj[u]) { dfs(dfs, v, u, w, 1, [&](int d, [[maybe_unused]] int cnt) { r[d] = inf; }); } for (auto [v, w] : adj[u]) { if (!done[v]) { self(self, v); } } }; centroid_decomposition(centroid_decomposition, 0); if (ans == inf) { ans = -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...