This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3,unroll-loops")
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
#define cont(x) {for(auto el:x) cout<<el<<' ';cout<<endl;}
#define contp(x) {for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;}
#define sp <<" "<<
#define mid (l+r)/2
#define endl '\n'
#define DEBUG(X) {cout<<#X<<' '<<(X)<<endl;}
#define carp(x,y) ((x%MOD)*(y%MOD))%MOD
#define topla(x,y) ((x%MOD)+(y%MOD))%MOD
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
const int MAXN=3e5+5;
const ll INF=INT_MAX;
const int MOD=1e9+7;
vii adj[MAXN];
ll n,k;
ll res;
pll t[MAXN];
set<pll> s[MAXN];
void merge(ll nd, ll kom){
if(s[nd].size()<s[kom].size()) swap(kom,nd);
//setteki elemanlar--> {dist,edge sayisi}
//adjdeki elemanlar--> {kom,dist}
auto aranan=k+2*t[nd].se;
auto cikar=t[nd].fi;
//önce cevabı bul
for(auto el:s[kom]){
auto deg=aranan-el.fi;
auto it=s[nd].lower_bound({deg,0});
auto bir=(*it).fi; //distance
auto iki=(*it).se; //no of edges
if(bir==deg){
res=min(res,iki+el.se-2*cikar);
}
}
//sonra insertle
for(auto el:s[kom]) s[nd].insert(el);
}
void dfs(ll nd,ll ata,ll h,ll edg){
t[nd]={edg,h};
for(auto el:adj[nd]){
auto kom=el.fi;
auto cost=el.se;
if(kom!=ata){
dfs(kom,nd,h+cost,edg+1);
merge(nd,kom);
}
}
auto aranan=k+t[nd].se;
auto cikar=t[nd].fi;
auto it=s[nd].lower_bound({aranan,0});
if((*it).fi==aranan){
res=min(res,(*it).se-cikar);
}
s[nd].insert({t[nd].se,t[nd].fi});
}
int best_path(int N, int K, int H[][2], int L[]){
//#define int long long
res=INF;
k=K;
n=N;
FOR(i,n-1){
adj[H[i][0]+1].pb({H[i][1]+1,L[i]});
adj[H[i][1]+1].pb({H[i][0]+1,L[i]});
}
dfs(1,0,0,0);
//#undef int
if(res==INF) res=-1;
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |