Submission #217526

#	Time	Username	Problem	Language	Result	Execution time	Memory
217526		T0p_	Race (IOI11_race)	C++14	0 / 100	13 ms	14592 KiB

race

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

#define pb push_back

struct edge
{
	int n, w;	
};

int k, ans = 1e9;
vector<edge> g[200002];
map<int, int> cnt[200002];

void dfs(int node, int par)
{
	for(edge x : g[node])
	{
		if(x.n == par) continue ;
		dfs(x.n, node);
	}
	for(edge x : g[node])
	{
		if(x.n == par) continue ;
		for(auto it : cnt[x.n])
		{
			if(k - it.first - x.w <= 0) continue ;
			if(cnt[node].count(k - it.first - x.w)) ans = min(ans, it.second + 1 + cnt[node][k-it.first-x.w]);
		}
		for(auto it : cnt[x.n])
		{
			if(it.first + x.w > k) continue ;
			if(cnt[node].count(it.first + x.w)) cnt[node][it.first+x.w] = min(cnt[node][it.first+x.w], it.second+1);
			else cnt[node][it.first+x.w] = it.second+1;
		}
	}
	if(cnt[node].count(k)) ans = min(ans, cnt[node][k]);
	cnt[node][0] = 0;
}

int best_path(int N, int K, int H[][2], int L[])
{
	k = K;
	for(int i=1 ; i<N ; i++)
	{
		g[H[i-1][0]+1].pb({H[i-1][1]+1, L[i-1]});
		g[H[i-1][1]+1].pb({H[i-1][0]+1, L[i-1]});
	}
	dfs(1, 0);
	printf(ans == 1e9 ? "-1\n" : "%d\n",ans);
	return N;
}

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