Submission #808479

#	Time	Username	Problem	Language	Result	Execution time	Memory
808479		SteGG	Race (IOI11_race)	C++17	43 / 100	3062 ms	133148 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

const int maxn = 1e6 + 5;
const int inf = 1e9 + 7;

int depth[maxn];
int road[maxn];
int n, k;
vector<pair<int, int>> tr[maxn];
int dp[maxn][105];
int result = inf;

void solve(int u, int p){
	for(auto node : tr[u]){
		int v = node.first;
		int w = node.second;
		if(v == p) continue;
		solve(v, u);

		for(int in = 0; in + w <= k; in++){
			int out = k - w - in;
			//cout << "Before : " << result << " " << dp[u][out] << " " << dp[v][in] << endl;
			result = min(result, dp[u][out] + dp[v][in] + 1);
			//cout << "After : " << result << endl;
		}

		for(int j = 0; j + w <= k; j++){
			dp[u][j + w] = min(dp[u][j + w], dp[v][j] + 1);
		}
	}
}

void dfs(int u, int p){
	for(auto node : tr[u]){
		int v = node.first;
		int w = node.second;
		if(v == p) continue;
		depth[v] = depth[u] + 1;
		road[v] = road[u] + w;
		dfs(v, u);
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N;
	k = K;
	for(int i = 0; i < n - 1; i++){
		int a, b, l;
		a = H[i][0];
		b = H[i][1];
		l = L[i];
		tr[a].push_back({b, l});
		tr[b].push_back({a, l});
	}

	if(k <= 100){
		for(int i = 0; i < n; i++){
			dp[i][0] = 0;
		}

		for(int i = 0; i < n; i++){
			for(int j = 1; j <= k; j++){
				dp[i][j] = inf;
			}
		}

		solve(0, -1);
	}else{
		for(int i = 0; i < n; i++){
			depth[i] = 0;
			road[i] = 0;
			dfs(i, -1);
			for(int j = 0; j < n; j++){
				if(road[j] == k && result > depth[j]){
					result = depth[j];
				}
			}
		}
	}

	if(result == inf){
		return -1;
	}else{
		return result;
	}
}

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