Submission #422215

#	Time	Username	Problem	Language	Result	Execution time	Memory
422215		ScarletS	Race (IOI11_race)	C++17	21 / 100	3091 ms	13716 KiB

race

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

const int N = 1<<18, INF = 1e9;
int k, x, y, ans = INF, dp[1<<20], sub[N];
array<int,2> a[N];
array<int,4> d[N];
vector<array<int,2>> e[N];
bitset<N> b;

void subDfs(int c)
{
	a[0]={c,-1};
	for (int i=0;i<x;++i)
	{
		sub[a[i][0]]=1;
		for (auto j : e[a[i][0]])
			if (j[0]!=a[i][1]&&!b[j[0]])
				a[x++]={j[0],a[i][0]};
	}
	for (int i=x-1;i>0;--i)
		sub[a[i][1]]+=sub[a[i][0]];
}

int findC(int c, int p, int t)
{
	bool ok;
	while (1)
	{
		ok=1;
		for (auto i : e[c])
			if (i[0]!=p&&!b[i[0]]&&sub[i[0]]>t)
			{
				p=c;
				c=i[0];
				ok=0;
				break;
			}
		if (ok)
			return c;
	}
}

void dfs(int c, int p, int h, int t)
{
	a[x++]={h,t};
	ans=min(ans,dp[k-h]+t);
	for (auto i : e[c])
		if (i[0]!=p&&h+i[1]<=k)
			dfs(i[0],c,h+i[1],t+1);
}

void dfs(int c, int p, int h)
{
	int z=1,t;
	d[0]={c,p,h,1};
	for (int i=0;i<z;++i)
	{
		c=d[i][0];p=d[i][1];h=d[i][2];t=d[i][3];
		a[x++]={h,t};
		ans=min(ans,dp[k-h]+t);
		for (auto j : e[c])
			if (j[0]!=p&&h+j[1]<=k)
				d[z++]={j[0],c,h+j[1],t+1};
	}
}

void solve(int n)
{
	x=1;
	subDfs(n);
	int c = findC(n,-1,sub[n]/2);
	b[c]=1;
	x=0;
	for (auto i : e[c])
		if (!b[i[0]]&&i[1]<=k)
		{
			y=x;
			dfs(i[0],c,i[1]);
			for (int j=y;j<x;++j)
				dp[a[j][0]]=min(dp[a[j][0]],a[j][1]);
		}
	for (int i=0;i<x;++i)
		dp[a[i][0]]=INF;
	for (auto i : e[c])
		if (!b[i[0]])
			solve(i[0]);
}

int best_path(int n, int K, int h[][2], int l[])
{
	k=K;
	for (int i=0;i<n-1;++i)
	{
		e[h[i][0]].push_back({h[i][1],l[i]});
		e[h[i][1]].push_back({h[i][0],l[i]});
	}
	for (int i=1;i<=k;++i)
		dp[i]=INF;
	solve(0);
	if (ans==INF)
		return -1;
	return ans;
}

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