Submission #898775

#	Time	Username	Problem	Language	Result	Execution time	Memory
898775		Muhammad_Aneeq	Race (IOI11_race)	C++17	21 / 100	3056 ms	18136 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 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,int h)
{
	if (val>reqval)
		return;
	cur.push_back({val,h});
	if (f.find(reqval-val)!=f.end())
		ans=min(ans,h+f[reqval-val]);
	for (auto [i,we]:nei[n])
	{
		if (!dead[i]&&i!=m)
		{
			dfs1(i,n,val+we,h+1);
		}
	}
}
void sol(int 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])
		{
			dfs1(i,-1,we,1);
			for (auto [j,w]:cur)
			{
				if (f.find(j)==f.end())
					f[j]=w;
				f[j]=min(f[j],w);
			}
		}
	}
	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: 0 / 22
• Subtask 4: 0 / 57