Submission #248869

#	Time	Username	Problem	Language	Result	Execution time	Memory
248869		eohomegrownapps	Race (IOI11_race)	C++14	100 / 100	439 ms	99580 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<ll,ll>>> adjlist; //n,l
vector<set<pair<ll,ll>>*> vset; //height,numnodes
vector<ll> prefsum;
vector<ll> height;
ll n,k;
ll INF = 1e18;

void dfs(ll node, ll par){
	for (auto p : adjlist[node]){
		if (p.first==par){continue;}
		prefsum[p.first]=prefsum[node]+p.second;
		height[p.first]=height[node]+1;
		dfs(p.first,node);
	}
}

ll minval(ll node, ll par){
	if (adjlist[node].size()==1&&par!=-1){
		////cout<<"x\n";
		vset[node]=new set<pair<ll,ll>>();
		vset[node]->insert({prefsum[node],height[node]});
		return INF;
	}
	ll mxv = INF;
	ll mxind = -1;
	ll mxsize = -1;
	for (auto p : adjlist[node]){
		ll i = p.first;
		if (i==par){continue;}
		mxv=min(mxv,minval(i,node));
		ll vs = vset[i]->size();
		////cout<<vs<<" "<<mxsize<<'\n';
		if (vs>mxsize){
			mxind=i;
			mxsize=vs;
		}
	}
	////cout<<mxind<<' '<<mxsize<<'\n';
	//merge everything llo vset[i]
	ll kv = (par==-1)?k:(k+2*prefsum[node]);
	for (auto p : adjlist[node]){
		ll i = p.first;
		if (i==par||i==mxind){continue;}
		for (auto hn : *vset[i]){
			ll heightfind = kv-hn.first;
			//can we find heightfind?
			auto f = vset[mxind]->lower_bound({heightfind,0});
			if (f!=vset[mxind]->end()&&f->first==heightfind){
				mxv=min(mxv,hn.second+f->second-2*height[node]);
			}
			vset[mxind]->insert(hn);
		}
	}
	//cout<<"check "<<k+prefsum[node]<<'\n';
	/*for (auto p : *vset[mxind]){
		//cout<<p.first<<" "<<p.second<<", ";
	}//cout<<'\n';*/
	auto f = vset[mxind]->lower_bound({k+prefsum[node],-1});
	if (f!=vset[mxind]->end()&&f->first==k+prefsum[node]){
		mxv=min(mxv,f->second-height[node]);
	}
	vset[node]=vset[mxind];
	vset[node]->insert({prefsum[node],height[node]});
	//cout<<node<<" "<<par<<": "<<mxv<<'\n';
	return mxv;
}

int best_path(int N, int K, int H[][2], int L[]){
	n=N;k=K;
	adjlist.resize(n);
	for (ll i = 0; i<n-1; i++){
		adjlist[H[i][0]].push_back({H[i][1],L[i]});
		adjlist[H[i][1]].push_back({H[i][0],L[i]});
	}
	vset.resize(n,NULL);
	prefsum.resize(n,0);
	height.resize(n,0);
	dfs(1,-1);
	ll mv = minval(1,-1);
	return (mv==INF)?-1:mv;
}

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