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