Submission #1274602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274602		saidpon	Race (IOI11_race)	C++20	100 / 100	1710 ms	55892 KiB

race

#include "bits/stdc++.h"

using namespace std;

#define pb push_back
#define pii pair<int, int>
#define fr first
#define sc second

const int inf = 1e9 + 7;

int best_path(int n, int k, int H[][2], int L[]){
	vector <vector<pii>> pon(n);

	for (int i = 0; i < n - 1; i++) {
		pon[H[i][0]].pb({H[i][1], L[i]});
		pon[H[i][1]].pb({H[i][0], L[i]});
	}
	
	vector <int> sz(n), ded(n);
	
	function<void(int, int)> szdfs = [&](int u, int p) {
		sz[u] = 1;
		
		for (auto [v, w]: pon[u]) {
			if (v == p || ded[v]) continue;
			
			szdfs(v, u);
			
			sz[u] += sz[v];
		}
	};
	
	function<int(int, int, int)> findcentr = [&](int u, int p, int m) {
		for (auto [v, w]: pon[u]) {
			if (v == p || ded[v]) continue;
			
			if (sz[v] > m / 2) return findcentr(v, u, m);
		}
		
		return u;
	};
	
	map <int, int> d;
	
	function<void(int, int, int, int)> soldfs = [&](int u, int p, int c, int dep) {
		if (d[k - c]) d[k] = (d[k] ? min(d[k], max(0, d[k - c]) + dep) : max(0, d[k - c]) + dep);
		
		for (auto [v, w]: pon[u]) if (v != p && !ded[v]) soldfs(v, u, c + w, dep + 1);
	};
	
	function<void(int, int, int, int)> updatedfs = [&](int u, int p, int c, int dep) {
		d[c] = (d[c] ? min(d[c], dep) : dep);
		
		for (auto [v, w]: pon[u]) if (v != p && !ded[v]) updatedfs(v, u, c + w, dep + 1);
	};
	
	int ans = inf;
	
	function<void(int)> sol = [&](int u) {
		szdfs(u, u);
		
		d.clear();
		d[0] = -1;
		
		for (auto [v, w]: pon[u]) {
			if (ded[v]) continue;
			
			soldfs(v, u, w, 1);
			updatedfs(v, u, w, 1);	
		}
		
		if (d[k]) ans = min(ans, d[k]);
		
		ded[u] = 1;
		
		for (auto [v, w]: pon[u]) if (!ded[v]) sol(findcentr(v, v, sz[v]));
	};
	
	sol(findcentr(0, 0, n));
	
	return (ans == inf ? -1 : ans);
}

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