Submission #898723

#	Time	Username	Problem	Language	Result	Execution time	Memory
898723		Faisal_Saqib	Race (IOI11_race)	C++17	100 / 100	587 ms	44572 KiB

race

#include <iostream>
#include <vector>
#include <map>
using namespace std;
const int N1=2e5+10;
const int inf=4e5;
int n,k,ans=inf;
vector<pair<int,int>> ma[N1];
int sz[N1];
bool done_for[N1];
void dfs_sz(int x,int p=-1)
{
	sz[x]=1;
	for(auto [y,w]:ma[x])
		if(y!=p)
		{
			dfs_sz(y,x);
			sz[x]+=sz[y];
		}
}
int current_n=0;
int find_centroid(int x,int p=-1)
{
	for(auto [y,w]:ma[x])
	{
		if(!done_for[y] and y!=p and sz[y]>(current_n/2))
		{
			sz[x]-=sz[y];
			sz[y]+=sz[x];
			return find_centroid(y,x);
		}
	}
	return x;
}
map<int,int> tmp;
void dfs_update(int x,long long su=0,int h=1,int p=-1)
{
	if(su>k)
		return;
	if(tmp.find(k-su)!=tmp.end())
		ans=min(ans,tmp[k-su]+h);
	for(auto [y,w]:ma[x])
		if(y!=p and !done_for[y])
			dfs_update(y,su+w,h+1,x);
}
void dfs_add(int x,long long su=0,int h=1,int p=-1)
{
	if(su>k)
		return;
	if(tmp.find(su)==tmp.end())
		tmp[su]=h;
	else
		tmp[su]=min(tmp[su],h);
	for(auto [y,w]:ma[x])
	{
		if(y!=p and !done_for[y])
		{
			dfs_add(y,su+w,h+1,x);
		}
	}
}
void solve(int x,int p=-1,int l=0)
{
	int c=find_centroid(x);
	done_for[c]=1;
	// Full working so now we do dfs
	// What we do is the we go 
	tmp.clear();
	tmp[0]=0;
	for(auto [y,w]:ma[c])
	{
		if(!done_for[y])
		{
			dfs_update(y,w,1,-1);
			dfs_add(y,w,1,-1);
		}
	}
	for(auto [y,w]:ma[c])
	{
		if(!done_for[y])
		{
			current_n=sz[y];
			solve(y,c,l+1);
		}
	}
}
int best_path(int n1, int k1, int h[][2], int l[])
{
	n=n1;
	k=k1;
	for(int i=0;i<(n-1);i++)
	{
		ma[h[i][0]].push_back({h[i][1],l[i]});
		ma[h[i][1]].push_back({h[i][0],l[i]});
	}
	dfs_sz(0);
	current_n=n;
	solve(0);
	if(ans==inf)
		ans=-1;
	return ans;
}

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