| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 971814 | khanhtb | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 998244353;
const ll inf = 1e18;
const ll base = 26;
const ll blocksz = 320;
const ll N = 1e6+8;
const ll lim = 1e5+8;
ll tin[N],tout[N],tdfs,d[N],sz[N],euler[N],ans = inf,n,k,h[N];
map<ll,ll> mn;
vpll g[N];
void init(ll u, ll p){
sz[u] = 1;
tin[u] = ++tdfs;
euler[tdfs] = u;
for(auto [v,w]:g[u]){
if(v == p) continue;
h[v] = h[u]+1;
d[v] = d[u]+w;
if(d[v] == k) ans = min(ans,h[v]);
init(v,u);
sz[u] += sz[v];
}
tout[u] = tdfs;
}
void sackadd(ll u){
if(!mn[d[u]]) mn[d[u]] = inf;
mn[d[u]] = min(mn[d[u]],h[u]);
}
void sackrmv(ll u){
mn[d[u]] = inf;
}
void dfs(ll u, ll p){
ll big = 0;
for(auto [v,w]:g[u]){
if(v == p) continue;
if(sz[v] > sz[big]) big = v;
}
for(auto [v,w]:g[u]){
if(v != p && v != big){
dfs(v,u);
for(ll i = tin[v]; i <= tout[v]; i++) sackrmv(euler[i]);
}
}
if(big) dfs(big,u);
if(!mn[d[u]+k]) mn[d[u]+k] = inf;
ans = min(ans,mn[d[u]+k]-h[u]);
sackadd(u);
for(auto [v,w]:g[u]){
if(v == big || v == p) continue;
for(ll i = tin[v]; i <= tout[v]; i++){
ll ch = euler[i];
ll len = k-d[ch]+2*d[u];
if(len < 0) continue;
if(!mn[len]) mn[len] = inf;
ans = min(ans,mn[len]+h[ch]-2*h[u]);
}
for(ll i = tin[v]; i <= tout[v]; i++){
ll ch = euler[i];
sackadd(ch);
}
}
}
void solve(){
cin >> n >> k;
for(ll i = 1; i < n; i++){
ll u,v,w;cin >> u >> v >> w;
u++,v++;
g[u].pb({v,w});
g[v].pb({u,w});
}
init(1,1);
dfs(1,1);
cout << ((ans >= 2e5)?-1:ans);
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
if(fopen("test.inp","r")){
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
}
int T = 1;
// cin >> T;
for(int tt = 1; tt <= T; tt++){
solve();
// cout << '\n';
}
}