# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1188768 | GoBananas69 | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <array>
using namespace std;
typedef long long ll;
vector<vector<pair<ll, ll>>> adj;
bool check(vector<ll> &pref, ll m, ll k) {
for (int i = 0; i<pref.size() - m; ++i) {
if (pref[i + m] - pref[i] == k) {
return true;
}
}
return false;
}
ll best_path(ll n, ll k, vector<array<int, 2>> h, vector<ll> s) {
adj.clear();
adj.resize(n);
for (int i = 0; i < n - 1; ++i) {
ll u = h[i][0], v = h[i][1], w = s[i];
adj[u].push_back({v, w});
}
ll l = 0, r = n;
vector<ll> pref(n, 0);
for (int i = 1; i<n; ++i) {
pref[i] = pref[i - 1] + s[i - 1];
}
while (l + 1 < r) {
ll m = (l + r) / 2;
if (check(pref, m, k)) {
r = m;
} else {
l = m;
}
}
return (r == n ? -1 : r);
}