Submission #865953

#	Time	Username	Problem	Language	Result	Execution time	Memory
865953		tamir1	Race (IOI11_race)	C++14	0 / 100	2 ms	10588 KiB

race

#include<bits/stdc++.h>
#define ll int
#define pp pair<ll,ll>
#define f first
#define s second
using namespace std;
ll N,K,L[200001],i,a,b,ans=200010,sz[200001],H[200001][2];
bitset<200001> mark;
map<ll,ll> mp;
vector<pp> G[200001];
ll getsize(ll a,ll p=-1){
	sz[a]=1;
	for(pp i:G[a]){
		if(p!=i.f && !mark[i.f]) 
			sz[a]+=getsize(i.f,a);
	}
	return sz[a];
}
ll centroid(ll a,ll p,ll n){
	for(pp i:G[a]){
		if(p!=i.f && sz[i.f]>n/2 && !mark[i.f])
			return centroid(i.f,a,n);
	}
	return a;
}
void dfs(ll a,ll p,ll dist,ll len,bool key){
	if(dist>K) return;
	if(dist==K){
		ans=min(ans,len);
		return;
	}
	if(key){
		if(mp[K-dist]) 
			ans=min(ans,len+mp[K-dist]);
	}
	else{
		if(!mp[dist]) mp[dist]=len;
		else mp[dist]=min(mp[dist],len);
	}
	for(pp i:G[a]){
		if(p!=i.f && !mark[i.f]){
			dfs(i.f,a,dist+i.s,len+1,key);
		}	
	}
}
void solve(ll a){
	ll n,cnt;
	n=getsize(a);
	cnt=centroid(a,0,n);
	mark[cnt]=1;
	mp.clear();
	for(pp i:G[cnt]){
		if(!mark[i.f]){
			dfs(i.f,cnt,i.s,1,1);
			dfs(i.f,cnt,i.s,1,0);
		}
	}
	for(pp i:G[cnt]){
		if(!mark[i.f])
			solve(i.f);
	}
}
ll best_path(ll N,ll K,ll H[][2],ll L[]){
	for(i=1;i<N;i++){
		a=H[i][0]+1;
		b=H[i][1]+1;
		G[a].push_back({b,L[i]});
		G[b].push_back({a,L[i]});
	}
	solve(1);
	if(ans==200010) return -1;
	return ans;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57