| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1148743 | son2008 | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 20
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define fii fi.fi
#define fis fi.se3
#define sfi se.fi
#define see se.se
#define base 29
int dx[]={0LL,0LL,1,-1,1,1,-1,-1};
int dy[]={1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=1e5+1;
const int mod=1e9+7;
int n,root,sz[maxn],f[maxn],h[maxn],q,par[maxn],dp[maxn],ans=1e18,mn[maxn*10],mx_h,k;
bool is_centroid[maxn];
vector<ii>a[maxn];
void dfs(int u,int cha)
{
sz[u]=1;
for(ii v:a[u])
{
if(v.fi==cha||is_centroid[v.fi])continue;
dfs(v.fi,u);
sz[u]+=sz[v.fi];
}
}
int find_centroid(int u,int tree_sz,int cha)
{
for(ii v:a[u])
if(v.fi!=cha&&!is_centroid[v.fi]&&sz[v.fi]>tree_sz/2) return find_centroid(v.fi,tree_sz,u);
return u;
}
void get(int u,int cha,int h,int w)
{
if(w>k)return;
ans=min(ans,mn[k-w]+h);
for(ii v:a[u])
{
if(v.fi==cha||is_centroid[v.fi])continue;
get(v.fi,u,h+1,w+v.se);
}
}
void update(int u,int cha,int h,int w)
{
if(w>k)return;
mn[w]=min(mn[w],h);
mx_h=max(mx_h,h);
for(ii v:a[u])
{
if(v.fi==cha||is_centroid[v.fi])continue;
update(v.fi,u,h+1,w+v.se);
}
}
void build_centroid(int u,int pre_centroid)
{
dfs(u,-1);
int centroid=find_centroid(u,sz[u],-1);
if(root==0)root=centroid;
mn[0]=0;
mx_h=0;
is_centroid[centroid]=true;
for(ii v:a[centroid])
{
if(!is_centroid[v.fi])
{
get(v.fi,centroid,0,0);
update(v.fi,centroid,0,0);
}
}
for(int i=0;i<=mx_h;i++)mn[i]=1e9;
for(ii v:a[centroid])
{
if(!is_centroid[v.fi])build_centroid(v.fi,centroid);
}
}
/*signed main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
{
int u,v,w;
cin>>u>>v>>w;
a[u].push_back({v,w});
a[v].push_back({u,w});
}
dfs(0,-1);
memset(mn,0x3f,sizeof(mn));
build_centroid(1,-1);
if(ans==1e18)cout<<-1;
else
cout<<ans;
}*/
int best_path(int N,int K,int H[][2],int w[])
{
k=K,n=N;
for(int i=0;i<n;i++)
{
a[H[i][0]].push_back({H[i][1],w[i]});
a[H[i][1]].push_back({H[i][0],w[i]});
}
dfs(0,-1);
memset(mn,0x3f,sizeof(mn));
build_centroid(1,-1);
if(ans==1e18)return -1;
else return ans;
}