| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 379098 | mariowong | 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>
using namespace std;
int n,m,u,z,w,ct[1000005],sum,ans,node,sz[200005];
vector <pair<int,int> > edge[200005];
vector <pair<int,int> > v;
bool vis[200005],del[200005],ok,cen[200005];
void dfs(int x){
vis[x]=true; sz[x]=1;
for (int i=0;i<edge[x].size();i++){
if (!vis[edge[x][i].first]){
dfs(edge[x][i].first);
sz[x]+=sz[edge[x][i].first];
}
}
}
void find_centroid(int x,int nowsz){
if (node != -1)
goto byew;
cen[x]=true;
for (int i=0;i<edge[x].size();i++){
if (sz[edge[x][i].first] < sz[x] && sz[edge[x][i].first]*2 > nowsz)
goto gg;
}
if ((nowsz-sz[x])*2 <= nowsz)
node=x;
gg:;
for (int i=0;i<edge[x].size();i++){
if (!cen[edge[x][i].first] && !del[edge[x][i].first] && node == -1)
find_centroid(edge[x][i].first,nowsz);
}
byew:;
}
void ggto(int x,int dis,int num){
vis[x]=true; ok=false; sz[x]=1;
for (int i=0;i<edge[x].size();i++){
if (!vis[edge[x][i].first] && !del[edge[x][i].first]){
ok=true;
ggto(edge[x][i].first,dis+edge[x][i].second,num+1);
sz[x]+=sz[edge[x][i].first];
}
}
if (!ok)
v.push_back(make_pair(dis,num));
}
void div_and_con(int x,int nowsz){
for (int i=0;i<n;i++){
vis[i]=false;
cen[i]=false;
}
for (int i=1;i<=m;i++){
ct[i]=1e9;
}
v.clear(); sz[x]=1;
for (int i=0;i<edge[x].size();i++){
if (!vis[edge[x][i].first] && !del[edge[x][i].first]){
v.clear();
ggto(edge[x][i].first,edge[x][i].second,1);
for (int j=0;j<v.size();j++){
if (v[j].first <= m)
ans=min(ans,ct[m-v[j].first]+v[j].second);
}
for (int j=0;j<v.size();j++){
if (v[j].first <= m)
ct[v[j].first]=min(ct[v[j].first],v[j].second);
}
sz[x]+=sz[edge[x][i].first];
}
}
for (int i=0;i<edge[x].size();i++){
if (!del[edge[x][i].first] && sz[edge[x][i].first] > 1){
node=-1;
find_centroid(edge[x][i].first,sz[edge[x][i].first]);
del[node]=true;
div_and_con(node,sz[edge[x][i].first]);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m; ans=1e9;
for (int i=1;i<n;i++){
cin >> u >> z >> w;
edge[u].push_back(make_pair(z,w));
edge[z].push_back(make_pair(u,w));
}
dfs(0);
for (int i=0;i<n;i++){
for (int j=0;j<edge[i].size();j++){
if (sz[edge[i][j].first] < sz[i] && sz[edge[i][j].first]*2 > n)
goto out;
}
if ((n-sz[i])*2 <= n){
del[i]=true;
div_and_con(i,n);
break;
}
out:;
}
if (ans == 1e9)
cout << "-1\n";
else
cout << ans << "\n";
return 0;
}