| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1172599 | versesrev | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
// 23:47
#include <vector>
#include <utility>
#include <functional>
int best_path(int N, int K, int H[][2], int L[]) {
if (N == 1) {
return -1;
}
std::vector<std::vector<std::pair<int, int>>> edges(N, std::vector<std::pair<int, int>>());
for (int i = 0; i < N - 1; ++i) {
edges[H[i][0]].emplace_back(H[i][1], L[i]);
edges[H[i][1]].emplace_back(H[i][0], L[i]);
}
int ans = N + 1;
std::vector<bool> exist(N, true);
std::vector<std::vector<int>> subtree_sizes;
std::vector<std::vector<int>> dists;
std::vector<std::vector<int>> depths;
std::function<void(int, int)> dc = [&](int dc_depth, int root) {
if (dc_depth >= subtree_sizes.size()) {
subtree_sizes.emplace_back(N, 0);
dists.emplace_back(N, 0);
depths.emplace_back(N, 0);
}
// find centroid
int g = std::invoke([&]{
// return root;
auto& subtree_size = subtree_sizes[dc_depth];
// std::function<int(int, int)> compute_size = [&](int v, int p) {
auto compute_size = [&](auto&& self, int v, int p) {
subtree_size[v] = 1;
for (auto [u, _] : edges[v]) {
if (not exist[u] or u == p) continue;
subtree_size[v] += self(self, u, v);
}
return subtree_size[v];
};
compute_size(compute_size, root, -1);
const int total_size = subtree_size[root];
// std::function<int(int, int)> get_centroid = [&](int v, int p) {
auto get_centroid = [&](auto&& self, int v, int p) {
for (auto [u, _] : edges[v]) {
if (not exist[u] or u == p) continue;
if (subtree_size[u] > total_size / 2) return self(self, u, v);
return v;
}
};
return get_centroid(get_centroid, root, -1);
});
exist[g] = false;
// dc(subtrees)
for (auto [u, _] : edges[g]) {
if (not exist[u]) continue;
dc(dc_depth + 1, u);
}
exist[g] = true; return;
// merge
// dfs to get dist
//. for each subtree
//. for each node
//. try to update ans d[node]
//. for each node
//. update query map
auto& dist = dists[dc_depth];
auto& depth = depths[dc_depth];
std::vector<int> nodes;
std::function<void(int, int)> dfs = [&](int v, int p) {
if (dist[v] > K) return;
nodes.push_back(v);
for (auto [u, w] : edges[v]) {
if (not exist[u] or u == p) continue;
dist[u] = dist[v] + w;
depth[u] = depth[v] + 1;
dfs(u, v);
}
};
std::unordered_map<int, int> min_length;
dist[g] = 0;
depth[g] = 0;
min_length[0] = 0;
for (auto [u, w] : edges[g]) {
if (not exist[u]) continue;
dist[u] = w;
depth[u] = 1;
nodes.clear();
dfs(u, g);
for (int v : nodes) {
auto it = min_length.find(K - dist[v]);
if (it != min_length.end()) {
ans = std::min(ans, depth[v] + it->second);
}
}
for (int v : nodes) {
auto it = min_length.find(dist[v]);
if (it == min_length.end() or depth[v] < it->second) {
min_length[dist[v]] = depth[v];
}
}
}
exist[g] = true;
};
dc(0, 0);
return ans == N + 1 ? -1 : ans;
}