Submission #954610

#	Time	Username	Problem	Language	Result	Execution time	Memory
954610		Em1L	Race (IOI11_race)	C++17	100 / 100	335 ms	81968 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using ll = long long;
using pii = std::pair<int, int>;

std::vector < std::vector < pii > > g;

std::vector < ll > dist;
std::vector < int > depth;

void DFS1(int v, int p, ll sum, int d) {
    dist[v] = sum;
    depth[v] = d;

    for (auto [u, w] : g[v])
        if (u != p)
            DFS1(u, v, sum + w, d + 1);
}

int len, ans = INT_MAX;

std::map < ll, int > DFS2(int v, int p) {
    std::map < ll, int > dp;

    dp[dist[v]] = depth[v];

    for (auto [u, w] : g[v])
        if (u != p) {
            auto sub = DFS2(u, v);

            if (sub.size() > dp.size())
                std::swap(sub, dp);

            for (auto [dist_, depth_] : sub)
                if (dp.count(len + 2 * dist[v] - dist_)) {
                    ans = std::min(ans, dp[len + 2 * dist[v] - dist_] + depth_ - 2 * depth[v]);
                }

            for (auto [dist, depth] : sub)
                if (!dp.count(dist))
                    dp[dist] = depth;
                else
                    dp[dist] = std::min(dp[dist], depth);
        }

    return dp;
}

int best_path(int N, int K, int H[][2], int L[]) {
    dist.resize(N);
    depth.resize(N);
    g.resize(N);

    for (int i = 0; i < N - 1; i++) {
        g[H[i][0]].push_back({ H[i][1], L[i] });
        g[H[i][1]].push_back({ H[i][0], L[i] });
    }

    DFS1(0, 0, 0, 0);

    len = K;
    DFS2(0, 0);

    return ans == INT_MAX ? -1 : ans;
}

// int main() {
//     int n, k; std::cin >> n >> k;

//     int h[n][2], l[n];

//     for (int i = 0; i < n - 1; i++)
//         std::cin >> h[i][0] >> h[i][1] >> l[i];

//     std::cout << best_path(n, k, h, l) << "\n";
// }

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