Submission #283604

#	Time	Username	Problem	Language	Result	Execution time	Memory
283604		TMJN	Race (IOI11_race)	C++17	100 / 100	2504 ms	67300 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
	int to,cost;
};

vector<edge>E[200000];
int N,K,res,c;
int tree_id[200000],subtree_size[200000],dist[200000];
ll cost[200000];

int get_centroid(int x,int from,int size,int id){
	subtree_size[x]=0;
	if(tree_id[x]!=id)return -1;
	subtree_size[x]=1;
	for(edge e:E[x]){
		if(e.to==from)continue;
		int p=get_centroid(e.to,x,size,id);
		if(p!=-1)return p;
		subtree_size[x]+=subtree_size[e.to];
	}
	int t=x;
	if(size-subtree_size[x]<=size/2){
		for(edge e:E[x]){
			if(subtree_size[e.to]>size/2)t=-1;
		}
	}
	else t=-1;
	return t;
}

void dfs(int x,int from,int id){
	if(tree_id[x]!=id)return;
	for(edge e:E[x]){
		if(e.to==from)continue;
		dist[e.to]=dist[x]+1;
		cost[e.to]=cost[x]+e.cost;
		dfs(e.to,x,id);
	}
}

void dfs2(vector<int>&v,int x,int from,int id){
	if(tree_id[x]!=id)return;
	v.push_back(x);
	for(edge e:E[x]){
		if(e.to==from)continue;
		dfs2(v,e.to,x,id);
	}
}

void F(vector<int>&v,int id){
	if(v.empty())return;
	c++;
	for(int i:v){
		tree_id[i]=id;
	}
	int cent=get_centroid(v.front(),v.front(),v.size(),id);
	dist[cent]=cost[cent]=0;
	dfs(cent,cent,id);
	vector<vector<int>>vv;
	for(edge e:E[cent]){
		vv.push_back({});
		dfs2(vv.back(),e.to,cent,id);
	}
	set<pair<pair<ll,int>,int>>st;
	for(int i:v){
		st.insert({{cost[i],dist[i]},i});
	}
	auto it=st.lower_bound({{K,-1},-1});
	if(it!=st.end()&&it->first.first==K){
		res=min(res,it->first.second);
	}
	for(vector<int>&V:vv){
		for(int i:V){
			st.erase({{cost[i],dist[i]},i});
		}
		for(int i:V){
			auto it=st.lower_bound({{K-cost[i],-1},-1});
			if(it!=st.end()&&it->first.first==K-cost[i]){
				res=min(res,it->first.second+dist[i]);
			}
		}
		for(int i:V){
			st.insert({{cost[i],dist[i]},i});
		}
	}
	for(vector<int>&V:vv){
		F(V,c);
	}
}


int best_path(int n, int k, int H[][2], int L[]){
	N=n;
	K=k;
	res=0xE869120;
	for(int i=0;i<N-1;i++){
		E[H[i][0]].push_back({H[i][1],L[i]});
		E[H[i][1]].push_back({H[i][0],L[i]});
	}
	vector<int>v;
	for(int i=0;i<N;i++){
		v.push_back(i);
	}
	F(v,c);
	if(res==0xE869120)res=-1;
	return res;
}

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