Submission #1194628

#TimeUsernameProblemLanguageResultExecution timeMemory
1194628olegmakRace (IOI11_race)C++20
100 / 100
242 ms75360 KiB
#include <bits/stdc++.h> using namespace std; int best_path(int n, int k, int edges[][2], int weights[]) { vector<vector<pair<int, int>>> g(n); for (int i = 0; i < n - 1; ++i) { const auto& e = edges[i]; g[e[0]].push_back({e[1], weights[i]}); g[e[1]].push_back({e[0], weights[i]}); } vector<long long> dist(n); vector<int> edge_cnt(n); auto dfs = [&](auto&& dfs, int u, int p) -> void { for (const auto [v, w] : g[u]) { if (v == p) { continue; } dist[v] = dist[u] + w; edge_cnt[v] = edge_cnt[u] + 1; dfs(dfs, v, u); } }; dfs(dfs, 0, -1); constexpr int INF = numeric_limits<int>::max(); int min_edges = INF; auto dfs2 = [&](auto&& dfs2, int u, int p) -> map<long long, int> { map<long long, int> u_stats; for (const auto [v, w] : g[u]) { if (v == p) { continue; } auto v_stats = dfs2(dfs2, v, u); if (u_stats.size() < v_stats.size()) { swap(u_stats, v_stats); } for (const auto v_stat : v_stats) { const auto l = k - v_stat.first + 2 * dist[u]; if (auto iter = u_stats.find(l); iter != u_stats.end()) { min_edges = min(min_edges, iter->second + v_stat.second - 2 * edge_cnt[u]); } } for (const auto v_stat : v_stats) { auto iter2 = u_stats.insert({v_stat.first, INF}).first; iter2->second = min(iter2->second, v_stat.second); } } auto iter2 = u_stats.insert({dist[u], edge_cnt[u]}).first; iter2->second = min(iter2->second, edge_cnt[u]); const auto l = k + dist[u]; if (auto iter = u_stats.find(l); iter != u_stats.end()) { min_edges = min(min_edges, iter->second - edge_cnt[u]); } return u_stats; }; dfs2(dfs2, 0, -1); return min_edges == INF ? -1 : min_edges; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...