Submission #1172582

#TimeUsernameProblemLanguageResultExecution timeMemory
1172582versesrevRace (IOI11_race)C++20
0 / 100
0 ms320 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, long long>>> edges; 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([&]{ auto& subtree_size = subtree_sizes[dc_depth]; std::function<int(int, int)> compute_size = [&](int v, int p) { subtree_size[v] = 1; for (auto [u, _] : edges[v]) { if (not exist[u] or u == p) continue; subtree_size[v] += compute_size(u, v); } return subtree_size[v]; }; compute_size(root, -1); const int total_size = subtree_size[root]; std::function<int(int, int)> get_centroid = [&](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 get_centroid(u, v); return v; } }; return get_centroid(root, -1); }); exist[g] = false; // dc(subtrees) for (auto [u, _] : edges[g]) { if (not exist[u]) continue; dc(dc_depth + 1, u); } // 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; }

Compilation message (stderr)

race.cpp: In lambda function:
race.cpp:46:7: warning: control reaches end of non-void function [-Wreturn-type]
   46 |       };
      |       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...