Submission #1211690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211690		orzorzorz	Race (IOI11_race)	C++20	21 / 100	478 ms	327680 KiB

race

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

#define ll long long
#define ff first
#define ss second

const int mxN = 2e5 + 5;
vector<pair<int, ll>> adj[mxN];
multiset<pair<ll, int>> s[mxN];
int K;

int dfs(int v, int fa) {
    s[v].insert({0, 0}); // Path of length 0 with 0 edges from v
    int min_edges = 1e9;

    for (auto [u, w] : adj[v]) {
        if (u == fa) continue;
        int child_min = dfs(u, v);

        // Paths entirely within u's subtree
        min_edges = min(min_edges, child_min);

        // Paths from v through u
        vector<pair<ll, int>> new_paths;
        for (auto [len, cnt] : s[u]) {
            ll new_len = len + w;
            int new_cnt = cnt + 1;
            if (new_len == K) {
                min_edges = min(min_edges, new_cnt);
            } else if (new_len < K) {
                new_paths.push_back({new_len, new_cnt});
            }
        }

        // Paths combining s[v] and s[u] through v
        for (auto [len1, cnt1] : s[u]) {
            ll need = K - w - len1;
            if (need < 0) continue;
            auto it = s[v].lower_bound({need, 0});
            if (it != s[v].end() && it->ff == need) {
                min_edges = min(min_edges, cnt1 + it->ss + 1);
            }
        }

        // Merge u's paths into v
        for (auto p : new_paths) {
            s[v].insert(p);
        }
    }

    return min_edges == 1e9 ? 1e9 : min_edges;
}

int best_path(int N, int K, int H[][2], int L[]) {
    ::K = K;
    for (int i = 0; i < N; i++) {
        adj[i].clear();
        s[i].clear();
    }
    for (int i = 0; i < N - 1; i++) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    int result = dfs(0, -1);
    return result == 1e9 ? -1 : result;
}

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