| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 405251 | jaaguptamme | 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 int long long
const int N=200005,M=20;
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
vector<pii>g[N];
vector<int>r[N],sub[N];
int pr[M][N],cst[M][N],dep[N],sz[N],n,k,dn[N],fa[N];
void D(int u,int p=-1){
for(auto el:g[u]){
auto v=el.first,w=el.second;
if(v==p)continue;
dep[v]=dep[u]+1;
D(v,u);
pr[0][v]=u;
cst[0][v]=w;
}
}
int calc(int u,int p=-1){
if(dn[u])return 0;
sz[u]=0;
for(auto el:g[u]){
auto v=el.first,w=el.second;
if(v==p)continue;
if(dn[v])continue;
sz[u]+=calc(v,u)+1;
}
return sz[u];
}
int cent(int u,int n,int p=-1){
for(auto el:g[u]){
auto v=el.first,w=el.second;
if(v==p)continue;
if(dn[v])continue;
if(sz[v]>=n/2)return cent(v,n,u);
}
return u;
}
void solve(int u,int p=-1){
if(dn[u])return;
calc(u,p);
int c=cent(u,sz[u],-1);
sub[c].push_back(c);
fa[c]=p;
if(p!=-1){
r[p].push_back(c);
int cur=c;
while(fa[cur]!=-1){
cur=fa[cur];
sub[cur].push_back(c);
}
//cout<<p<<' '<<c<<'\n';
}
dn[c]=1;
for(auto el:g[c]){
auto v=el.first,w=el.second;
if(dn[v])continue;
solve(v,c);
}
}
pii dist(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int ans=0,ln=0;
for(int j=M-1;j>=0;j--){
if(dep[u]-(1<<j)>=dep[v]){
ans+=cst[j][u];
ln+=1<<j;
u=pr[j][u];
}
}
if(u==v)return {ans,ln};
for(int j=M-1;j>=0;j--){
if(pr[j][u]!=pr[j][v]){
ans+=cst[j][u]+cst[j][v];
u=pr[j][u];
v=pr[j][v];
ln+=2*(1<<j);
}
}
ans+=cst[0][u]+cst[0][v];
ln+=2;
return {ans,ln};
}
vector<ll>kaugus(N,0),pikkus(N,0);
int32_t main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=1;i<n;i++){
int u,v,c;cin>>u>>v>>c;
g[u].push_back({v,c});
g[v].push_back({u,c});
}
D(0,-1);
for(int j=1;j<M;j++){
for(int i=0;i<n;i++){
pr[j][i]=pr[j-1][pr[j-1][i]];
cst[j][i]=cst[j-1][i]+cst[j-1][pr[j-1][i]];
}
}
solve(0,-1);
/*for(int i=0;i<n;i++){
cout<<i<<": ";
for(auto j:sub[i])cout<<j<<' ';
cout<<'\n';
}*/
int res=INT_MAX;
for(int i=0;i<n;i++){
//vector<vector<pii>>vals;
//cout<<i<<endl;
for(auto j:sub[i]){
auto el=dist(i,j);
kaugus[j]=el.first;
pikkus[j]=el.second;
//cout<<i<<' '<<j<<' '<<kaugus[j]<<' '<<pikkus[j]<<'\n';
}
map<int,int>mp;
mp[0]=0;
for(auto j:r[i]){
for(auto l:sub[j]){
if(mp.count(k-kaugus[l]))res=min(res,pikkus[l]+mp[k-kaugus[l]]);
}
for(auto l:sub[j]){
if(!mp.count(kaugus[l]))mp[kaugus[l]]=INT_MAX;
mp[kaugus[l]]=min(mp[kaugus[l]],pikkus[l]);
}
}
}
if(res!=INT_MAX)cout<<res<<' ';
else cout<<-1<<endl;
return 0;
}