| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 768752 | Caubethieunang | 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 LOG 20
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define FIRST_BIT(mask) __builtin_ctz((mask)&(-mask))
#define ERASE_BIT(mask) (mask)^((mask)&(-mask))
#define left _left
#define right _right
#define task "t"
using namespace std;
const int INF=1e9;
const int iat=1e6+9;
const int mod=1e9+7;
const int MAX=15e5;
void fast_IO()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
}
int n,k,dem;
struct CentroidDecomposition
{
int child[iat],check[iat],cntedge[iat];
set <pair<int,int>> g[iat];
void addEdge(int u, int v, int w)
{
g[u].insert({v,w}); g[v].insert({u,w});
}
int dfs(int u, int par)
{
child[u]=1;
for(auto it : g[u])
{
if(it.first!=par)child[u]+=dfs(it.first,u);
}
return child[u];
}
int centroid(int u, int par, int sz)
{
for(auto it : g[u])
{
if(it.first!=par)
{
if(child[it.first]>sz/2)return centroid(it.first,u,sz);
}
}
return u;
}
int dfs2(int u, int par, int dist, int cnt, int t, vector <pair<int,int>> &v)
{
int haha=k-dist,ans=INF;
if(haha>=0 && check[haha]==t)ans=min(ans,cnt+cntedge[haha]);
if(dist<=k)
{
v.push_back({dist,cnt});
for(auto it : g[u])
{
if(it.first!=par)ans=min(ans,dfs2(it.first,u,it.second+dist,cnt+1,t,v));
}
}
return ans;
}
int solve(int u, int par)
{
int sz=dfs(u,par);
int node=centroid(u,par,sz);
int ans=INF;
int t=++dem;
check[0]=t,cntedge[0]=0;
for(auto it : g[u])
{
vector <pair<int,int>> tmp;
ans=min(ans,dfs2(it.first,node,it.second,1,t,tmp));
for(auto IT : tmp)
{
if(check[IT.first]!=t || (check[IT.first]==t && cntedge[IT.first]>IT.second))
{
check[IT.first]=t;
cntedge[IT.first]=IT.second;
}
}
}
vector <pair<int,int>> tmp(g[node].begin(),g[node].end());
for(auto it : tmp)
{
g[node].erase(it); g[it.first].erase({node,it.second});
ans=min(ans,solve(it.first,node));
}
return ans;
}
}cd;
signed main()
{
fast_IO();
cin>>n>>k;
for(int i=1; i<n; i++)
{
int u,v,w;
cin>>u>>v>>w;
cd.addEdge(u,v,w);
}
int ans=cd.solve(0,-1);
cout<<(ans==INF ? -1 : ans);
}