| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1112653 | ntdaccode | 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 fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod=1e9+7;
const int M=1e6+10;
const int N=2e5+10;
int n,k;
vector<ii> ke[N];
bool dd[N];
int sz[N];
int child(int u,int p=0)
{
sz[u]=1;
for(auto [v,w]:ke[u]) if(v!=p&&!dd[v]) sz[u]+=child(v,u);
return sz[u];
}
int centroid(int u,int p=0)
{
for(auto [v,w]:ke[u]) if(v!=p&&!dd[v]&&sz[v]>n/2) return centroid(v,u);
return u;
}
int mi[M],kq=1e9;
vector<int> wdel;
void dfs(int u,int tt,int val,int depth,int p=0)
{
if(val>k) return ;
if(!tt) {
kq=min(kq,depth+mi[k-val]);
}
else {
if(mi[val]==1e9) wdel.pb(val);
mi[val]=min(mi[val],depth);
}
for(auto [v,w] :ke[u]) if(v!=p&&!dd[v]) dfs(v,tt,val+w,depth+1,u);
}
void solve(int u)
{
n=child(u);
int root=centroid(u);
dd[root]=true;
for(auto [v,w] : ke[root]) {
if(!dd[v]) {
dfs(v,0,w,1);
dfs(v,1,w,1);
}
}
for(int v: wdel) mi[v]=1e9;
wdel.clear();
for(auto [v,w] :ke[root]){
if(!dd[v]) solve(v);
}
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#define task "1"
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n >> k;
fori(i,1,n-1)
{
int u,v,w;
cin >> u >> v >> w;
u++;
v++;
ke[u].pb({v,w});
ke[v].pb({u,w});
}
fori(i,1,1e6) mi[i]=1e9;
mi[0]=0;
solve(1);
cout << (kq==1e9 ? -1 : kq) ;
}