Submission #1196217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196217		agast	Race (IOI11_race)	C++20	0 / 100	0 ms	320 KiB

race

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define f first
#define s second
#include "race.h"

int best_path(int n, int k, int h[][2], int l[]) {
	vector<vector<pair<int, int>>> adj(n);
	for (int i = 0; i < n-1; i++) {
		const auto &[u, v] = h[i];
		adj[u].push_back({v, l[i]});
		adj[v].push_back({u, l[i]});
	}
	vector<multiset<pair<int, int>>> paths(n);
	int ans = INT_MAX;
	auto dfs = [&] (int node, int prev, auto &&dfs) -> void {
		if (adj[node].size() == 1 && adj[node][0].f == prev) {
			return;
		}
		for (auto [next, w] : adj[node]) {
			if (next != prev) {
				paths[node].insert({w, 1});
				dfs(next, node, dfs);
				if (paths[node].size() < paths[next].size()) swap(paths[node], paths[next]);
				for (auto i : paths[next]) {
					ll t1 = i.f + w;
					int t2 = i.s + 1;
					auto it = paths[node].lower_bound({k - t1, -1});
					if (t1 == k) {
						ans = min(ans, t2);
					} else if (it != paths[node].end() && it->first == k-t1) {
						ans = min(ans, t2 + it->second);
					}
					auto it2 = paths[node].lower_bound({t1, -1});
					if (it2 == paths[node].end()) {
						paths[node].insert({t1, t2});
					} else if (it2->second >= t2) {
						paths[node].erase(it2);
						paths[node].insert({t1, t2});
					}
				}
			}
		}
	};
	dfs(0, -1, dfs);
	return ans != INT_MAX ? ans : -1;
}

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