| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 229872 | DavidDamian | Race (IOI11_race) | C++11 | 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 "race.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge
{
ll to;
ll w;
};
vector<edge> adjList[200005];
ll Size[200005];
ll getSize(ll u,ll p)
{
Size[u]=1;
for(edge e: adjList[u]){
ll v=e.to;
if(v==p) continue;
Size[u]+=getSize(v,u);
}
return Size[u];
}
ll k;
ll minimum=LLONG_MAX;
map<ll,ll>* sack[200005];
typedef pair<ll,ll> pii;
void dfs(ll u,ll p,ll distRoot,ll depth)
{
//cout<<u<<" "<<p<<" "<<distRoot<<" "<<depth<<endl;
ll greatest=0,bigChild=-1;
for(edge e: adjList[u]){
ll v=e.to;
if(v==p) continue;
//cout<<"V"<<v<<endl;
dfs(v,u,distRoot+e.w,depth+1);
if(Size[v]>greatest){
greatest=Size[v];
bigChild=v;
}
}
if(bigChild==-1)
sack[u]=new map<ll,ll>;
else
sack[u]=sack[bigChild];
for(edge e: adjList[u]){
ll v=e.to;
if(v==p) continue;
if(v==bigChild) continue;
for(pii x: *sack[v]){
ll dist=x.first-distRoot;
if((*sack[u]).find(k-dist+distRoot)!=(*sack[u]).end()){
ll length=(*sack[u])[k-dist+distRoot]+x.second;
length-=2*depth;
minimum=min(minimum,length);
}
if((*sack[u])[x.first]==0) (*sack[u])[x.first]=x.second;
else{
ll length=(*sack[u])[x.first];
(*sack[u])[x.first]=min(length,x.second);
}
}
}
if((*sack[u]).find(k+distRoot)!=(*sack[u]).end()){
ll length=(*sack[u])[k+distRoot];
length-=depth;
minimum=min(minimum,length);
}
if((*sack[u])[distRoot]==0) (*sack[u])[distRoot]=depth;
else{
ll length=(*sack[u])[distRoot];
(*sack[u])[distRoot]=min(length,depth);
}
//cout<<u<<" min"<<minimum<<endl;
//for(pii x: *sack[u]){
// cout<<x.first<<" "<<x.second<<endl;
//}
}
ll best_path(ll n, ll K, ll H[][2], ll L[])
{
k=K;
for(ll i=0;i<n-1;i++){
ll a=H[i][0]+1;
ll b=H[i][1]+1;
ll w=L[i];
adjList[a].push_back({b,w});
adjList[b].push_back({a,w});
}
/*for(ll i=1;i<=n;i++){
cout<<i<<":";
for(edge e: adjList[i]){
cout<<e.to<<" ";
}
cout<<endl;
}*/
getSize(1,0);
dfs(1,0,0,0);
return (minimum!=LLONG_MAX)? minimum : -1;
}