Submission #864094

#	Time	Username	Problem	Language	Result	Execution time	Memory
864094		20163070	Race (IOI11_race)	C++14	31 / 100	116 ms	40528 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;

const int N=4e5+10,INF=1e9;

int n,k;
int h[N],e[N],ne[N],w[N],idx;
int sz[N],mx[N],vis[N],sum,root;
pair<int,int> s[N];
int f[N];
int ans;
int tp;
int q[N];

void add(int a,int b,int c)
{
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void getroot(int u,int fa)
{
	sz[u]=1;
	mx[u]=0;
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j==fa||vis[j]) continue;
		getroot(j,u);
		sz[u]+=sz[j];
		mx[u]=max(mx[u],sz[j]);
	}
	mx[u]=max(mx[u],sum-sz[u]);
	if(mx[root]>mx[u]) root=u;
}

void getdis(int u,int fa,int d,int p)
{
	if(d>k) return;
	s[++tp]=make_pair(d,p);
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j==fa||vis[j]) continue;
		getdis(j,u,d+w[i],p+1);
	}
}

void solve(int u)
{
	int cnt=0;
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(vis[j]) continue;
		tp=0;
		getdis(j,u,w[i],1);
		for(int i=1;i<=tp;i++) ans=min(ans,s[i].second+f[k-s[i].first]);
		for(int i=1;i<=tp;i++) f[q[++cnt]=s[i].first]=min(f[s[i].first],s[i].second);
	}
	for(int i=1;i<=cnt;i++) f[q[i]]=INF;
}

void dfs(int u)
{
	vis[u]=1;
	f[0]=0;
	solve(u);
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(vis[j]) continue;
		root=0;
		sum=sz[j];
		getroot(j,u);
		dfs(root);
	}
}

int best_path(int N, int K, int tt[][2], int l[])
{
	n=N,k=K;
	memset(h,-1,sizeof h);
	for(int i=0;i<n-1;i++)
	{
		++tt[i][0],++tt[i][1];
		add(tt[i][0],tt[i][1],l[i]);
		add(tt[i][1],tt[i][0],l[i]);
	}
	for(int i=0;i<=k;i++) f[i]=INF;
	ans=mx[0]=INF;
	root=0;
	sum=n;
	getroot(1,0);
	dfs(root);
	if(ans==INF) return -1;
	return ans;
}

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