제출 #898783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
898783		Muhammad_Aneeq	경주 (Race) (IOI11_race)	C++17	100 / 100	617 ms	42948 KiB

race

#include <vector>
#include <set>
#include <map>
#include "race.h"
using namespace std;
int const MAXN=2e5+10;
vector<pair<int,int>>nei[MAXN]={};
int reqval=0,ans=1e9+10;
bool dead[MAXN]={};
int sz[MAXN]={};
int h[MAXN]={};
void dfs(int n,int m=-1)
{
	sz[n]=1;
	for (auto [i,we]:nei[n])
	{
		if (!dead[i]&&i!=m)
		{
			dfs(i,n);
			sz[n]+=sz[i];
		}
	}
}
int find_centroid(int n,int m,int root)
{
	for (auto [i,we]:nei[n])
	{
		if (!dead[i]&&i!=m&&sz[i]*2>sz[root])
			return find_centroid(i,n,root);
	}
	return n;
}
map<int,int>f;
vector<pair<int,int>>cur;
void dfs1(int n,int m,int val)
{
	cur.push_back({val,h[n]});
	if (val>reqval)
		return;
	if (f.find(reqval-val)!=f.end())
		ans=min(ans,h[n]+f[reqval-val]);
	for (auto [i,we]:nei[n])
	{
		if (!dead[i]&&i!=m)
		{
			h[i]=h[n]+1;
			dfs1(i,n,val+we);
		}
	}
}
void sol(int n)
{
	dfs(n);
	if (sz[n]==1)
		return;
	n=find_centroid(n,-1,n);
	dead[n]=1;
	cur={};
	f.clear();
	f[0]=0;
	for (auto [i,we]:nei[n])
	{
		if (!dead[i])
		{
			h[i]=1;
			dfs1(i,-1,we);
			for (auto [j,w]:cur)
			{
				if (f.find(j)==f.end())
					f[j]=w;
				else
					f[j]=min(f[j],w);
			}
			cur={};
		}
	}
	for (auto [i,we]:nei[n])
	{
		if (!dead[i])
			sol(i);
	}
}
int best_path(int n, int K, int H[][2], int L[])
{
	reqval=K;
	for (int i=0;i<n-1;i++)
	{
		int u=H[i][0],v=H[i][1];
		nei[u].push_back({v,L[i]});
		nei[v].push_back({u,L[i]});
	}
	sol(0);
	ans=(ans==1e9+10?-1:ans);
	return ans;
}

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