Submission #131116

#	Time	Username	Problem	Language	Result	Execution time	Memory
131116		eohomegrownapps	Race (IOI11_race)	C++14	100 / 100	598 ms	82936 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int> > > adjlist;
//weight, node
vector<pair<int,int> > distdepth;
vector<int> subtreesize;
vector<set<pair<int,int> > > paths;
//contains distance, depth
vector<int> use;
int currentMin;
int k;
int distances(int start, int parent){
	int sumtrees = 0;
	for (auto p : adjlist[start]){
		if (p.second==parent){
			continue;
		}
		distdepth[p.second]=make_pair(distdepth[start].first+p.first,distdepth[start].second+1);
		sumtrees+=distances(p.second,start);
	}
	return subtreesize[start]=sumtrees+1;
}

void dfs(int start, int parent){
	int maxsub = -1;
	int maxind = -1;
	for (auto p : adjlist[start]){
		if (p.second==parent){
			continue;
		}
		dfs(p.second,start);
		if (maxsub<subtreesize[p.second]){
			maxind=p.second;
			maxsub=subtreesize[p.second];
		}
	}
	//cout<<start<<"===="<<parent<<endl;
	auto st = distdepth[start];
	//cout<<st.first<<" "<<st.second<<endl;
	if (maxind==-1){
		paths[use[start]].insert(distdepth[start]);
		return;
	}
	use[start]=use[maxind];
	//cout<<"added "<<distdepth[start].first<<" "<<distdepth[start].second<<" to "<<use[start]<<endl;
	//cout<<"using "<<use[start]<<endl;
	for (auto p : adjlist[start]){
		if (p.second==maxind){
			continue;
		}
		for (auto s : paths[use[p.second]]){
			//cout<<"insert "<<s.first<<" "<<s.second<<endl;
			//check if it matches something in paths[use[maxind]]
			auto it = paths[use[start]].lower_bound(make_pair(k+st.first*2-s.first,0));
			if (it!=paths[use[start]].end()&&(*it).first==k+st.first*2-s.first){
				currentMin=min(currentMin,s.second+(*it).second-2*st.second);
			}
		}
		for (auto s : paths[use[p.second]]){
			//add to set
			paths[use[start]].insert(s);
		}
	}
	auto it = paths[use[start]].lower_bound(make_pair(k+st.first,0));
	if (it!=paths[use[start]].end()&&(*it).first==k+st.first){
		currentMin=min(currentMin,(*it).second-st.second);
	}
	paths[use[start]].insert(distdepth[start]);
}

int best_path(int N, int K, int H[][2], int L[]) {
	k=K;
	adjlist.resize(N);
	for (int i = 0; i<N-1; i++){
		adjlist[H[i][0]].push_back(make_pair(L[i],H[i][1]));
		adjlist[H[i][1]].push_back(make_pair(L[i],H[i][0]));
	}
	distdepth.resize(N,make_pair(-1,-1));
	subtreesize.resize(N,-1);
	distdepth[0]=make_pair(0,0);
	distances(0,-1);
	paths.resize(N);
	use.resize(N);
	for (int i = 0; i<N; i++){
		use[i]=i;
	}
	currentMin=N;
	dfs(0,-1);
	if (currentMin==N){
		return -1;
	} else {
		return currentMin;
	}
}

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