| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 147322 | mosiashvililuka | Race (IOI11_race) | C++14 | 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 mk make_pair
#define pll pair <long long, long long>
using namespace std;
long long a,b,c,d,e,pas=999999999999999999LL,k,pi,p[200009],dp[200009],cnt,dep[200009],msh[200009],koka;
bool was[200009];
vector <pair <long long, long long> > v[200009];
pair <long long, long long> z[1000009];
void dfs(long long q, long long w){
pi++;
p[pi]=q;
dp[q]=1;
msh[q]=w;
for(vector <pll>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it).first==w||was[(*it).first]==1) continue;
dfs((*it).first,q);
dp[q]+=dp[(*it).first];
}
}
void dfs2(long long q, long long w, long long r){
dep[q]=dep[w]+1;
if(r<=k&&z[k-r].second==cnt){
if(pas>dep[q]+z[k-r].first){
// cout<<q<<" "<<z[k-r].second<<" "<<koka<<endl;
pas=dep[q]+z[k-r].first;
}
}
for(vector <pll>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it).first==w||was[(*it).first]==1) continue;
dfs2((*it).first,q,(*it).second+r);
}
}
void dfs3(long long q, long long w, long long r){
if(r<=k){
if(z[r].second==cnt){
if(z[r].first>dep[q]) z[r].first=dep[q];
}else{
z[r].first=dep[q];
z[r].second=cnt;
}
}
for(vector <pll>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if((*it).first==w||was[(*it).first]==1) continue;
dfs3((*it).first,q,(*it).second+r);
}
}
void rec(long long q){
cnt++;
pi=0;
dfs(q,0);
long long zx=0;
for(long long h=1; h<=pi; h++){
bool bo=0;
for(vector <pll>::iterator it=v[p[h]].begin(); it!=v[p[h]].end(); it++){
if(was[(*it).first]==1||msh[p[h]]==(*it).first) continue;
if(dp[(*it).first]>pi/2){
bo=1;
break;
}
}
if(pi-dp[p[h]]>pi/2) bo=1;
if(bo==0){
zx=p[h];
break;
}
}
z[0].first=0;
z[0].second=cnt;
dep[zx]=0;koka=zx;
for(vector <pll>::iterator it=v[zx].begin(); it!=v[zx].end(); it++){
if(was[(*it).first]==0) dfs2((*it).first,zx,(*it).second);
if(was[(*it).first]==0) dfs3((*it).first,zx,(*it).second);
}
was[zx]=1;
for(vector <pll>::iterator it=v[zx].begin(); it!=v[zx].end(); it++){
if(was[(*it).first]==0) rec((*it).first);
}
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>k;
for(b=1; b<a; b++){
cin>>c>>d>>e;
c++;
d++;
v[c].push_back(mk(d,e));
v[d].push_back(mk(c,e));
}
rec(1);
if(pas==999999999999999999LL) cout<<-1; else cout<<pas;
return 0;
}