Submission #1263683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263683		EntityPlantt	Race (IOI11_race)	C++20	100 / 100	215 ms	104972 KiB

race

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

vector<vector<pair<int, int>>> g;
int ans, k;

unordered_map<int, int> *dfs(int u, int p, int l, int d) {
	vector sets = {new unordered_map{pair{l, d}}};
	for (auto &[v, w] : g[u]) {
		if (v == p) continue;
		sets.push_back(dfs(v, u, l + w, d + 1));
	}
	auto ret = *max_element(sets.begin(), sets.end(), [](auto &a, auto &b) { return a->size() < b->size(); });
	for (auto s : sets) {
		if (ret == s) continue;
		for (auto &x : *s) {
			if (ret->count(k + 2 * l - x.first)) ans = min(ans, (*ret)[k + 2 * l - x.first] + x.second - 2 * d);
		}
		for (auto &x : *s) {
			if (ret->count(x.first)) (*ret)[x.first] = min((*ret)[x.first], x.second);
			else (*ret)[x.first] = x.second;
		}
		delete s;
	}
	return ret;
}

int best_path(int N, int K, int H[][2], int L[]) {
	ans = 1e9;
	k = K;
	g.clear();
	g.resize(N);
	for (int i = 0; i < N - 1; i++) {
		g[H[i][0]].push_back({H[i][1], L[i]});
		g[H[i][1]].push_back({H[i][0], L[i]});
	}
	delete dfs(0, 0, 0, 0);
	return ans == 1e9 ? -1 : ans;
}

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