제출 #898710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
898710		Faisal_Saqib	경주 (Race) (IOI11_race)	C++17	21 / 100	258 ms	262144 KiB

race

#include <iostream>
#include <vector>
#include "race.h"
using namespace std;
const int N1=2e5+1;
const int K1=101;
const int inf=1e6;
int ans=inf,wnt;
vector<pair<int,int>> ma[N1];
int dp_up[N1][K1];
int dp_down[N1][K1][2];
void dfs_down(int x,int p=-1)
{
	dp_down[x][0][0]=dp_down[x][0][1]=0;
	for(auto [y,w]:ma[x])
	{
		if(y!=p)
		{
			dfs_down(y,x);
			for(int kp=0;(kp+w)<=wnt;kp++)
			{
				if(dp_down[x][kp+w][0]>(1+dp_down[y][kp][0]))
				{
					dp_down[x][kp+w][1]=dp_down[x][kp+w][0];
					dp_down[x][kp+w][0]=dp_down[y][kp][0]+1;
				}
				else if(dp_down[x][kp+w][1]>(1+dp_down[y][kp][0]))
				{
					dp_down[x][kp+w][1]=dp_down[y][kp][0]+1;
				}
			}
		}
	}
}
void dfs_up(int x,int p=-1)
{
	for(auto [y,w]:ma[x])
	{
		if(y!=p)
		{
			for(int kp=0;(kp+w)<=wnt;kp++)
			{
				dp_up[y][kp+w]=dp_up[x][kp]+1;
				if((kp-(w))>=0 and dp_down[x][kp][0]==(dp_down[y][kp-w][0]+1))
				{
					dp_up[y][kp+w]=min(dp_up[y][kp+w],dp_down[x][kp][1]+1);
				}
				else
				{
					dp_up[y][kp+w]=min(dp_up[y][kp+w],dp_down[x][kp][0]+1);
				}
			}
			dfs_up(y,x);
		}
	}
}
void dfs(int x,int p=-1,long long su=0,int h=0)
{
	if(su==wnt)
		ans=min(ans,h);
	for(auto [y,w]:ma[x])
		if(y!=p)
			dfs(y,x,(su+w),h+1);
}
int best_path(int n, int k, int h[][2], int l[])
{
	wnt=k;
	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]});
	}
	if(n<=1000)
	{
		for(int i=0;i<n;i++)
			dfs(i);
		if(ans==inf)
			ans=-1;
		return ans;
	}
	else
	{
		for(int i=0;i<n;i++)
			for(int j=1;j<=k;j++)
				dp_down[i][j][0]=dp_down[i][j][1]=dp_up[i][j]=inf;
		dfs_down(0);
		dfs_up(0);
		for(int i=0;i<n;i++)
		{
			ans=min(ans,dp_down[i][k][0]);
			ans=min(ans,dp_up[i][k]);
		}
		if(ans==inf)
			ans=-1;
		return ans;
	}
	return -1;
}

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