| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1147949 | Kodik | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ss second
#define ff first
typedef long long ll;
#define ll ll
using pi = array<ll, 2>;
const ll MOD = 1e9+7;
ll n, k;
const ll maxn = 2e5;
vector<pair<ll,ll>> g[maxn];
ll sz[maxn];
pi node[maxn];
map<ll,ll> len_to_dep[maxn];
void dfs_sz(ll v, ll p, ll d, ll l){
sz[v] = 1;
node[v] = {l, d};
for(auto &[w,u] : g[v]){
if(u!=p){
dfs_sz(u, v, d+1, l+w);
sz[v] += sz[u];
}
}
}
ll ans = 1e9;
void dfs(ll v, ll p){
ll mx = -1, bigChild = -1;
for(auto& [w, u] : g[v]){
if(u!=p&&sz[u]>mx){
mx = sz[u];
bigChild = u;
}
if(u!=p){
dfs(u, v);
}
}
if(bigChild!=-1){
swap(len_to_dep[v], len_to_dep[bigChild]);
}
if(len_to_dep[v].count(node[v][0])>0) len_to_dep[v][node[v][0]] = min(len_to_dep[v][node[v][0]], node[v][1]);
else len_to_dep[v][node[v][0]] = node[v][1];
for(auto &[w, u] : g[v]){
if(u!=p&&u!=bigChild){
for(auto &[l, d] : len_to_dep[u]){
ll seek = k-l+node[v][0];
if(len_to_dep[v].count(seek)>0){
ans = min(ans, d+len_to_dep[v][seek]-2*node[v][1]);
}
}
for(auto &[l, d] : len_to_dep[u]){
if(len_to_dep[v].count(l)>0) len_to_dep[v][l] = min(len_to_dep[v][l], d);
else len_to_dep[v][l] = d;
}
}
}
if(len_to_dep[v].count(k)>0) ans = min(ans, len_to_dep[v][k]);
}
int best_path(na, ka, h, l){
ios::sync_with_stdio(false);
cin.tie(nullptr);
n = na, k = ka;
for(ll i = 0; i < n-1; ++i){
ll x; cin >> x;
g[h[i][0]].push_back({x, h[i][1]});
g[h[i][1]].push_back({x, h[i][0]});
}
dfs_sz(0,-1,0,0);
dfs(0,-1);
if(ans==1e9) ans = -1;
cout << ans << '\n';
return 0;
}