Submission #898767

#	Time	Username	Problem	Language	Result	Execution time	Memory
898767		Muhammad_Aneeq	Race (IOI11_race)	C++17	43 / 100	3083 ms	59484 KiB

race

#include <vector>
#include <set>
#include <map>
#include "race.h"
using namespace std;
int const MAXN=2e5+10;
vector<int>nei[MAXN]={};
int reqval=0,ans=1e9+10;
bool dead[MAXN]={};
int sz[MAXN]={};
int h[MAXN]={};
map<pair<int,int>,int>d;
void dfs(int n,int m=-1)
{
	sz[n]=1;
	for (auto i: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:nei[n])
	{
		if (!dead[i]&&i!=m&&sz[i]*2>sz[root])
			return find_centroid(i,n,root);
	}
	return n;
}
map<long long,int>f;
vector<pair<long long,int>>cur;
void dfs1(int n,int m,long long 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:nei[n])
	{
		if (!dead[i]&&i!=m)
		{
			h[i]=h[n]+1;
			dfs1(i,n,val+d[{i,n}]);
		}
	}
}
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:nei[n])
	{
		if (!dead[i])
		{
			h[i]=1;
			dfs1(i,-1,d[{i,n}]);
			for (auto [j,w]:cur)
			{
				if (f.find(j)==f.end())
					f[j]=w;
				f[j]=min(f[j],w);
			}
		}
	}
	for (auto i: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);
		nei[v].push_back(u);
		d[{u,v}]=d[{v,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: 0 / 57