Submission #865946

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

race

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