| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 935948 | vjudge1 | 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>
using namespace std;
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define M 1000000007 //998244353 //
#define ll long long
#define pa pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define pi acos(-1.0)
#define vi vector<int>
#define vll vector<ll>
#define fr(i,n,j) for(i=j;i<=n;i++)
#define rfr(i,n,j) for(i=n;i>=j;i--)
#define ct continue;
#define yo cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define all(v) v.begin(),v.end()
#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int ar[500005],br[500005],kk;
vector<pa>adj[500001];
map<int,int> cnt[200001];
ll sz[500005],mx[500005],level[500006],dist[500005],ans;
vector<int>sub[500005];
void dfs(int child,int par,int flag)
{
for(auto u:adj[child])
{
if(u.ff==par)ct;
if(mx[child]==u.ff)ct;
dfs(u.ff,child,0);
}
if(mx[child]!=-1)
{
int u=mx[child];
dfs(u,child,1);
swap(sub[child],sub[u]);
}
sub[child].pb(child);
cnt[dist[child]][level[child]]++;
for(auto u:adj[child])
{
if(u.ff==par)ct;
if(mx[child]==u.ff)ct;
for(auto u1:sub[u.ff])
{
sub[child].pb(u1);
ll tmp=kk+2*dist[child]-dist[u1];
if(cnt[tmp].size())
{
auto it=cnt[tmp].rbegin();
ans=min(ans,(*it).ff+level[u1]-2*level[child]);
}
cnt[dist[u1]][level[u1]]++;
}
}
if(cnt[dist[child]+kk].size())
{
auto it=cnt[dist[child]+kk].rbegin();
ans=min(ans,(*it).ff-level[child]);
}
if(flag==0)
{
for(auto u:sub[child])
{
cnt[dist[u]][level[u]]--;
if(cnt[dist[u]][level[u]]==0)cnt[dist[u]].erase(level[u]);
}
}
}
void dfs2(int child,int par)
{
int tmp=0,big=-1;
sz[child]=0;
for(auto u:adj[child])
{
if(u.ff==par)ct;
level[u.ff]=level[child]+1;
dist[u.ff]=dist[child]+u.ss;
dfs2(u.ff,child);
if(sz[u.ff]>tmp)tmp=sz[u.ff],big=u.ff;
sz[child]+=sz[u.ff];
}
mx[child]=big;
sz[child]++;
}
int main()
{
fast;
ll te,n,m,i,j,k,w1,x,y,z,l2,k2,k1,q,l,r;
te=1;
//cin>>te;
fr(w1,te,1)
{
cin>>n>>kk;
fr(i,n,2)
{
cin>>x>>y>>z;
adj[x].pb({y,z});
adj[y].pb({x,z});
}
dfs2(0,-1);
ans=INT_MAX;
dfs(0,-1,1);
if(ans==INT_MAX)ans=-1;
cout<<ans<<endl;
}
}