Submission #884691

#	Time	Username	Problem	Language	Result	Execution time	Memory
884691		tamir1	Race (IOI11_race)	C++14	100 / 100	1037 ms	49192 KiB

race

#include "race.h"
#include<bits/stdc++.h>
#define ll int
#define pp pair<ll,ll>
#define f first
#define s second
using namespace std;
ll i,a,b,ans=200010,sz[200001],k;
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);
	}
}
int best_path(int N,int K,int H[][2],int L[]){
	k=K;
	for(i=0;i<N-1;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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57