Submission #491430

#	Time	Username	Problem	Language	Result	Execution time	Memory
491430		FireGhost1301	Race (IOI11_race)	C++17	100 / 100	449 ms	31320 KiB

race

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

const int N = 2e5 + 3;
int n, k;
vector<pair<int, int>> g[N];
bool vst[N];
int sz[N], min_edge[5 * N], ans = N;
vector<int> tmp;

int get_sz(int u, int p) {
    sz[u] = 1;
    for (auto [v, w]: g[u]) if (v != p && !vst[v])
        sz[u] += get_sz(v, u);
    return sz[u];
}

int centroid(int u, int p, int csz) {
    for (auto [v, w]: g[u]) if (v != p && !vst[v]) {
        if (sz[v] > csz / 2) return centroid(v, u, csz);
    }
    return u;
}

void dfs(int u, int p, int cur_len, int cnt, bool get_ans) {
    if (cur_len > k) return;
    if (get_ans) ans = min(ans, cnt + min_edge[k - cur_len]);
    else {
        tmp.push_back(cur_len);
        min_edge[cur_len] = min(min_edge[cur_len], cnt);
    }
    for (auto [v, w]: g[u]) if (v != p && !vst[v])
        dfs(v, u, cur_len + w, cnt + 1, get_ans);
}

void build_cd(int u) {
    u = centroid(u, 0, get_sz(u, 0));
    vst[u] = true;
    for (auto [v, w]: g[u]) if (!vst[v]) {
        dfs(v, u, w, 1, 1);
        dfs(v, u, w, 1, 0);
    }
    ans = min(ans, min_edge[k]);
    while (!tmp.empty()) {
        min_edge[tmp.back()] = N;
        tmp.pop_back();
    }
    for (auto [v, w]: g[u]) if (!vst[v])
        build_cd(v);
}

int solve() {
    for (int i = 0; i < 5 * N; ++i)
        min_edge[i] = N;
    build_cd(1);
    return (ans != N ? ans : -1);
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N, k = K;
    for (int i = 0; i < N - 1; ++i) {
        g[H[i][0] + 1].emplace_back(H[i][1] + 1, L[i]);
        g[H[i][1] + 1].emplace_back(H[i][0] + 1, L[i]);
    }
    return solve();
}

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