Submission #1206391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206391		Captain_Georgia	Race (IOI11_race)	C++20	100 / 100	623 ms	37700 KiB

race

#include "race.h"

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

const int MAXN = 1e6 + 6;

int best_path(int N, int K, int H[][2], int L[]) {
    vector<array<int, 2>> g[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]});
    }

    int res = 1e9 + 7, mx = 0;
    vector<int> used(N, 0), sub(N, 0), dist(MAXN, 0);
    function<void(int, int)> dfs_init = [&](int si, int pi) -> void {
        sub[si] = 1;
        for (auto [ti, wi] : g[si]) if (ti != pi && used[ti] == 0) {
            dfs_init(ti, si);
            sub[si] += sub[ti];
        }
    };
    function<int(int, int, int)> get_centr = [&](int si, int pi, int sz) -> int {
        for (auto [ti, wi] : g[si]) if (used[ti] == 0 && ti != pi && sub[ti] * 2 >= sz) {
            return get_centr(ti, si, sz);
        }
        return si;
    };
    function<void(int, int, int, int)> calc = [&](int si, int pi, int depth, int len) -> void {
        if (len > K) return;
        if (len == K) res = min(res, depth);

        mx = max(mx, len);
        if (dist[K - len] != 0) res = min(res, dist[K - len] + depth);

        for (auto [ti, wi] : g[si]) if (ti != pi && used[ti] == 0) {
            calc(ti, si, depth + 1, len + wi);
        }
    };
    function<void(int, int, int, int)> update = [&](int si, int pi, int depth, int len) -> void {
        if (len > K) return;

        if (dist[len] == 0) dist[len] = depth;
        else dist[len] = min(dist[len], depth);

        for (auto [ti, wi] : g[si]) if (ti != pi && used[ti] == 0) {
            update(ti, si, depth + 1, len + wi);
        }
    };
    function<void(int)> decompose = [&](int si) -> void {
        dfs_init(si, si);
        if (sub[si] == 1) return;
        int centr = get_centr(si, si, sub[si]);
        used[centr] = 1;

        mx = 0;
        for (auto [ti, wi] : g[centr]) if (used[ti] == 0) {
            calc(ti, centr, 1, wi);
            update(ti, centr, 1, wi);
        }
        for (int i = 0;i <= mx;i ++) dist[i] = 0;

        for (auto [ti, wi] : g[centr]) if (used[ti] == 0) {
            decompose(ti);
        }
    };
    decompose(0);
    if (res == 1e9 + 7) return -1;
    return res;
}

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