Submission #364738

#	Time	Username	Problem	Language	Result	Execution time	Memory
364738		ogibogi2004	Race (IOI11_race)	C++14	100 / 100	954 ms	54252 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=2e5+6;
const int MAXK=1e6+6;
vector<pair<int,ll> >g[MAXN];
vector<int>g1[MAXN];
int n,k;
bool f[MAXN];
int st[MAXN],root;
ll minh[MAXK],ans=MAXN+2;
int rankc[MAXN];
vector<int>updated;
void dfs(int u,int p)
{
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		dfs(v.first,u);
	}
}
void dfs1(int u,int p)
{
	st[u]=1;
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		if(f[v.first])continue;
		dfs1(v.first,u);
		st[u]+=st[v.first];
	}
}
int find(int u,int p,int t)
{
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		if(f[v.first])continue;
		if(st[v.first]>t/2)
		{
			return find(v.first,u,t);
		}
	}
	return u;
}
void decompose(int u,int p)
{
	dfs1(u,-1);
	int c=find(u,-1,st[u]);
	if(p!=-1)
	{
		rankc[c]=rankc[p]+1;
		g1[p].push_back(c);
	}
	else 
	{
		root=c;
		rankc[c]=1;
	}
	f[c]=1;
	for(auto v:g[c])
	{
		if(f[v.first])continue;
		decompose(v.first,c);
	}
}
void dfs2(int u,int p,int maxrank,int d,int d1)
{
	updated.push_back(d1);
	minh[d1]=min(minh[d1],(ll)d);
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		if(rankc[v.first]>=maxrank)continue;
		if(v.second+d1>k)continue;
		dfs2(v.first,u,maxrank,d+1,d1+v.second);
	}
}
void dfs3(int u,int p,int maxrank,int d,int d1)
{
	ans=min(ans,minh[k-d1]+d);
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		if(rankc[v.first]>=maxrank)continue;
		if(v.second+d1>k)continue;
		dfs3(v.first,u,maxrank,d+1,d1+v.second);
	}
}
int best_path(int N, int K, int H[][2], int L[])
{
	memset(f,0,sizeof(f));
	n=N;k=K;
	for(int i=1;i<=n;++i)g[i].clear();
	for(int i=0;i<N-1;++i)
	{
		g[H[i][0]+1].push_back({H[i][1]+1,L[i]});
		g[H[i][1]+1].push_back({H[i][0]+1,L[i]});
	}
	ans=n+2;
	dfs(1,0);
	decompose(1,-1);
	for(int i=0;i<MAXK;++i)minh[i]=n+2;
	for(int i=1;i<=n;++i)rankc[i]=n-rankc[i]+1;
	for(int i=1;i<=n;++i)
	{
		minh[0]=0;
		updated.clear();
		updated.push_back(0);
		for(auto v:g[i])
		{
			if(rankc[v.first]>=rankc[i])continue;
			if(v.second>k)continue;
			dfs3(v.first,i,rankc[i],1,v.second);
			dfs2(v.first,i,rankc[i],1,v.second);
		}
		for(auto u:updated)minh[u]=n+2;
	}
	if(ans>n)return -1;
	return ans;
}

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