Submission #248865

#	Time	Username	Problem	Language	Result	Execution time	Memory
248865		eohomegrownapps	경주 (Race) (IOI11_race)	C++14	43 / 100	420 ms	78700 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<int,int>>> adjlist; //n,l
vector<set<pair<int,int>>*> vset; //height,numnodes
vector<int> prefsum;
vector<int> height;
int n,k;
int INF = 1e9;

void dfs(int node, int 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);
	}
}

int minval(int node, int par){
	if (adjlist[node].size()==1&&par!=-1){
		////cout<<"x\n";
		vset[node]=new set<pair<int,int>>();
		vset[node]->insert({prefsum[node],height[node]});
		return INF;
	}
	int mxv = INF;
	int mxind = -1;
	int mxsize = -1;
	for (auto p : adjlist[node]){
		int i = p.first;
		if (i==par){continue;}
		mxv=min(mxv,minval(i,node));
		int vs = vset[i]->size();
		////cout<<vs<<" "<<mxsize<<'\n';
		if (vs>mxsize){
			mxind=i;
			mxsize=vs;
		}
	}
	////cout<<mxind<<' '<<mxsize<<'\n';
	//merge everything into vset[i]
	int kv = (par==-1)?k:(k+2*prefsum[node]);
	for (auto p : adjlist[node]){
		int i = p.first;
		if (i==par||i==mxind){continue;}
		for (auto hn : *vset[i]){
			int 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],0});
	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 (int 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(0,-1);
	int mv = minval(0,-1);
	return (mv==INF)?-1:mv;
}

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