| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 716351 | sktime | Race (IOI11_race) | C++17 | 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>
#include <ext/pb_ds/assoc_container.hpp>
#define PI 3.14159265
#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define vi vector<ll>
#define loop(i,a,b) for(int i=(a);i<=(b);i++)
#define looprev(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define log(args...) {string _s=#args;replace(_s.begin(),_s.end(),',',' ');stringstream _ss(_s);istream_iterator<string> _it(_ss);err(_it,args);}
#define logarr(arr,a,b) for(int z=(a);z<=(b);z++) cerr<<(arr[z])<<" ";cerr<<endl;
using namespace std;
using namespace __gnu_pbds;
void err(istream_iterator<string> it){}
template<typename T,typename... Args>
void err(istream_iterator<string> it,T a,Args... args){
cerr<<*it<<" = "<<a<<endl;
err(++it,args...);
}
template<class T> void debug(set<T> S){cerr<<"[ ";for(auto i:S) cerr<<i<<" ";cerr<<"] "<<endl;}
template<class T> void debug(multiset<T> S){cerr<<"[ ";for(auto i:S) cerr<<i<<" ";cerr<<"] "<<endl;}
template<class T> void debug(unordered_set<T> S){cerr<<"[ ";for(auto i:S) cerr<<i<<" ";cerr<<"] "<<endl;}
template<class T,class X> void debug(T *arr,X s,X e){cerr<<"[ ";loop(i,s,e) cerr<<arr[i]<<" ";cerr<<"] "<<endl;}
template<class T,class V> void debug(pair<T,V> p){cerr<<"{";cerr<<p.ff<<" "<<p.ss<<"}"<<endl;}
template<class T,class V> void debug(vector<pair<T,V>> v){cerr<<"[ "<<endl;for(auto i:v) debug(i);cerr<<"]"<<endl;}
template<class T> void debug(vector<T> v){cerr<<"[ ";for(auto i:v) cerr<<i<<" ";cerr<<"] "<<endl;}
template<class T> void debug(vector<vector<T>> v){cerr<<"[ "<<endl;for(auto i:v) debug(i);cerr<<"] "<<endl;}
typedef tree<int, null_type, less<int>,
rb_tree_tag, tree_order_statistics_node_update> ordered_set;
vi primes(){
int N=3e6;
vi isPrime(N+5,1);
isPrime[0]=0;
isPrime[1]=0;
loop(i,2,N){
if(isPrime[i]==0) continue;
int z=2*i;
while(z<N){
isPrime[z]=0;
z+=i;
}
}
return isPrime;
}
vi *getfactors(){
int N=2e5;
vi *factors=new vi[N+5];
loop(i,1,N){
for(int j=i;j<=N;j+=i){
factors[j].pb(i);
}
}
// time complexity O(nlogn)
return factors;
}
const int mod=998244353;
ll *getfactorial(){
int m=2e5;
ll *fact=new ll[m+1];
fact[0]=1;
loop(i,1,m){
fact[i]=(fact[i-1]*i)%mod;
}
// time complexity O(n)
return fact;
}
ll *fac;
ll power(ll a,ll b,ll m=mod){
if(b==0) return 1;
if(b==1) return a;
ll ans=power(a,b/2);
ans=(1ll*ans*ans)%m;
if(b%2==1){
ans=(1ll*ans*a)%m;
}
return ans;
}
ll nCr(ll n,ll r,int m=mod){
if(n<r) return 0;
ll ans=fac[n];
ans=(ans*power(fac[n-r],m-2))%m;
ans=(ans*power(fac[r],m-2))%m;
return ans;
}
int gcd(int a,int b){
if(b==0) return a;
if(a==0) return b;
return gcd(b,a%b);
}
const int N=2e5+5;
int n,k;
vector<pii> adjlst[N];
vi vis(N),sz(N);
int dfs(int v,int p=-1){
sz[v]=1;
for(auto temp:adjlst[v]){
int i=temp.ff;
int w=temp.ss;
if(i==p || vis[i]) continue;
sz[v]+=dfs(i,v);
}
return sz[v];
}
int getC(int v,int p,int s){
for(auto temp:adjlst[v]){
int i=temp.ff;
int w=temp.ss;
if(i==p || vis[i]) continue;
if(sz[i]*2>s) return getC(i,v,s);
}
return v;
}
map<ll,ll> mpp;
ll ans=1e18;
void dfs2(int v,int p,int w1,int depth){
if(mpp.find(k-w1)!=mpp.end()){
ans=min(ans,depth+mpp[k-w1]);
}
for(auto temp:adjlst[v]){
int i=temp.ff;
int w=temp.ss;
if(i==p || vis[i]) continue;
dfs2(i,v,w1+w,depth+1);
}
}
void dfs3(int v,int p,int w1,int depth){
if(mpp.find(w1)==mpp.end()){
mpp[w1]=depth;
}
for(auto temp:adjlst[v]){
int i=temp.ff;
int w=temp.ss;
if(i==p || vis[i]) continue;
dfs2(i,v,w1+w,depth+1);
}
}
int createTree(int v){
int c=getC(v,-1,dfs(v));
// log(c);
vis[c]=1;
for(auto temp:adjlst[c]){
int i=temp.ff;
int w=temp.ss;
if(vis[i]){
continue;
}
// log(i);
dfs2(i,v,w,1);
dfs3(i,v,w,1);
}
mpp.clear();
// log(ans);
for(auto temp:adjlst[c]){
int i=temp.ff;
int w=temp.ss;
if(vis[i]) continue;
createTree(i);
}
}
void test_case(){
cin>>n>>k;
vi h1(n+1),h2(n+1);
loop(i,1,n-1){
cin>>h1[i]>>h2[i];
}
loop(i,1,n-1){
int c;
cin>>c;
int a=h1[i],b=h2[i];
adjlst[a].pb({b,c});
adjlst[b].pb({a,c});
}
createTree(1);
if(ans!=1e18) cout<<ans<<endl;
else cout<<-1<<endl;
}
int main(){
boost
int t=1;
// cin>>t;
while(t--){
test_case();
}
}