# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1166553 | akamizane | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
const int maxn = 2e5 + 5;
map<int,int> info[maxn];
int d[maxn], sum[maxn];
vector<pair<int,int>> ad[maxn];
int N, K, res;
void pre(int u, int p, int val, int h){
info[u][val] = h;
sum[u] = val;
d[u] = h;
for (auto [v, w] : ad[u]){
if (v == p) continue;
pre(v, u, val + w, h + 1);
}
}
void dfs(int u, int p){
int need = K + 2 * sum[u];
for (auto [v, w] : ad[u]){
if (v == p) continue;
dfs(v, u);
if (info[u].size() < info[v].size()){
swap(info[u], info[v]);
}
for (auto [val, h] : info[v]){
if (info[u].find(need - val) != info[u].end() ){
res = min(res, info[u][need - val] + h - 2 * d[u]);
}
}
for (auto [val, h] : info[v]){
if (info[u].find(val) == info[u].end()){
info[u][val] = h;
}
else info[u][val] = min(info[u][val], h);
}
}
}
int best_path(int n, int k, int edges[][2], int weights[]) {
if (k == 1) { return 0; }
N = n;
K = k;
res = INT_MAX;
for (int i = 0; i < n - 1; i++) {
int u = edges[i][0];
int v = edges[i][1];
ad[u].push_back(make_pair(v, weights[i]));
ad[v].push_back(make_pair(u, weights[i]));
}
pre(0, -1, 0, 0);
dfs(0, -1);
return res == INT_MAX ? -1 : res;
}