Submission #1194627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194627		olegmak	Race (IOI11_race)	C++20	100 / 100	221 ms	75396 KiB

race

#include <bits/stdc++.h>

using namespace std;

int best_path(int n, int k, int edges[][2], int weights[]) {
	if (k == 1) { return 0; }
    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;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57