Submission #1005746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005746		thinknoexit	Race (IOI11_race)	C++17	100 / 100	277 ms	109136 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
vector<pair<int, int>> adj[N];
set<pair<ll, int>> s[N];
int ans = 1e9, K;
void dfs(int v, int p, ll val, int c) {
    s[v].insert({ val,c });
    for (auto& x : adj[v]) {
        if (x.first == p) continue;
        dfs(x.first, v, val + x.second, c + 1);
        if (s[x.first].size() > s[v].size()) swap(s[x.first], s[v]);
        for (auto& y : s[x.first]) {
            auto it = s[v].lower_bound({ K + 2 * val - y.first,0 });
            if (it == s[v].end()) continue;
            if (it->first == K + 2 * val - y.first) ans = min(ans, it->second + y.second - 2 * c);
        }
        for (auto& y : s[x.first]) {
            s[v].insert(y);
        }
    }
}
int best_path(int n, int k, int h[][2], int l[]) {
    for (int i = 0;i < n - 1;i++) {
        adj[h[i][0] + 1].push_back({ h[i][1] + 1, l[i] });
        adj[h[i][1] + 1].push_back({ h[i][0] + 1, l[i] });
    }
    K = k;
    dfs(1, 0, 0, 0);
    if (ans == 1e9) return -1;
    return ans;
}

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