Submission #237853

#	Time	Username	Problem	Language	Result	Execution time	Memory
237853		T0p_	Race (IOI11_race)	C++14	43 / 100	3079 ms	54140 KiB

race

#include <bits/stdc++.h>
using namespace std;
#include "race.h"
 
#define pb push_back
 
struct edge
{
	int node, weight;	
};
 
int k, ans = 1e9;
vector<edge> g[200002];
map<int, int> dp[200002];
 
void dfs(int now, int par)
{
	for(auto x : g[now])
	{
		if(x.node == par) continue ;
		dfs(x.node, now);
	}
	for(auto x : g[now])
	{
		if(x.node == par) continue ;
		for(auto it : dp[x.node])
		{
			int a = x.weight + it.first;
			int b = k - a;
			if(b <= 0) continue ;
			if(dp[now].count(b)) ans = min(ans, dp[now][b] + it.second + 1);
		}
		for(auto it : dp[x.node])
		{
			int w = it.first + x.weight;
			if(w > k) continue ;
			else if(w == k) ans = min(ans, it.second + 1);
			else if(dp[now].count(w)) dp[now][w] = min(dp[now][w], it.second + 1);
			else dp[now][w] = it.second + 1;
		}
		dp[x.node].clear();
	}
	dp[now][0] = 0;
}
 
int best_path(int N, int K, int H[][2], int L[])
{
	k = K;
	for(int i=0 ; i<N-1 ; i++)
	{
		int u = H[i][0] + 1, v = H[i][1] + 1, w = L[i];
		g[u].pb({v, w}), g[v].pb({u, w});
	}
	dfs(1, 0);
	if(ans == 1e9) ans = -1;
	return ans;
}

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