Submission #693184

#	Time	Username	Problem	Language	Result	Execution time	Memory
693184		leeh18	Race (IOI11_race)	C++17	43 / 100	3051 ms	25704 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

int best_path(int N, int K, int H[][2], int L[]) {
    vector<vector<pair<int, int>>> adj(N);
    for (auto i = 0; i < N - 1; ++i) {
        auto u = H[i][0];
        auto v = H[i][1];
        adj[u].emplace_back(v, L[i]);
        adj[v].emplace_back(u, L[i]);
    }
    constexpr auto inf = numeric_limits<int>::max() / 2;
    vector<int> subtree_size(N), r(K + 1, inf);
    vector<bool> done(N);
    r[0] = 0;
    auto ans = inf;
    auto dfs_size = [&](auto self, int u, int p) -> int {
        auto &ret = subtree_size[u];
        ret = 1;
        for (auto [v, w] : adj[u]) {
            if (v != p && !done[v]) {
                ret += self(self, v, u);
            }
        }
        return ret;
    };
    auto dfs_centroid = [&](auto self, int u, int p, int sz) -> int {
        for (auto [v, w] : adj[u]) {
            if (v != p && !done[v] && sz / 2 < subtree_size[v]) {
                return self(self, v, u, sz);
            }
        }
        return u;
    };
    auto dfs_dist = [&](auto self, int u, int p, int d, int cnt,
                        vector<pair<int, int>> &dist) -> void {
        if (K < d) {
            return;
        }
        dist.emplace_back(d, cnt);
        for (auto [v, w] : adj[u]) {
            if (v != p && !done[v]) {
                self(self, v, u, d + w, cnt + 1, dist);
            }
        }
    };
    auto centroid_decomposition = [&](auto self, int u) -> void {
        auto sz = dfs_size(dfs_size, u, u);
        u = dfs_centroid(dfs_centroid, u, u, sz);
        done[u] = true;
        vector<vector<pair<int, int>>> dists;
        for (auto [v, w] : adj[u]) {
            vector<pair<int, int>> dist;
            dfs_dist(dfs_dist, v, u, w, 1, dist);
            dists.emplace_back(move(dist));
        }
        for (const auto &dist : dists) {
            for (auto [d, cnt] : dist) {
                ans = min(ans, r[K - d] + cnt);
            }
            for (auto [d, cnt] : dist) {
                r[d] = min(r[d], cnt);
            }
        }
        for (const auto &dist : dists) {
            for (auto [d, cnt] : dist) {
                r[d] = inf;
            }
        }
        for (auto [v, w] : adj[u]) {
            if (!done[v]) {
                self(self, v);
            }
        }
    };
    centroid_decomposition(centroid_decomposition, 0);
    if (ans == inf) {
        ans = -1;
    }
    return ans;
}

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