Submission #1239535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239535		ssitaram	Race (IOI11_race)	C++20	100 / 100	276 ms	76124 KiB

race

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

typedef long long ll;
typedef long double ld;

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) {
		adj[h[i][0]].push_back({h[i][1], l[i]});
		adj[h[i][1]].push_back({h[i][0], l[i]});
	}
	vector<set<pair<ll, int>>> at(n);
	vector<pair<ll, int>> add(n);
	int ans = INT32_MAX;
	auto dfs = [&](auto&& self, int node, int p) -> void {
		at[node].insert({0, 0});
		for (pair<int, int>& c : adj[node]) {
			if (c.first == p) continue;
			self(self, c.first, node);
			add[c.first].first += c.second;
			++add[c.first].second;
			if (at[node].size() < at[c.first].size()) {
				swap(at[node], at[c.first]);
				swap(add[node], add[c.first]);
			}
			for (pair<ll, int> i : at[c.first]) {
				ll other = (k - (i.first + add[c.first].first)) - add[node].first;
				auto it = at[node].lower_bound({other, INT32_MIN});
				if (it != at[node].end() && it->first == other) {
					ans = min(ans, i.second + it->second + add[c.first].second + add[node].second);
				}
			}
			for (pair<ll, int> i : at[c.first]) {
				at[node].insert({i.first + add[c.first].first - add[node].first, i.second + add[c.first].second - add[node].second});
			}
			at[c.first].clear();
		}
	};
	dfs(dfs, 0, -1);
	return (ans == INT32_MAX ? -1 : ans);
}

/*int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int h[][2] = {{0, 1}, {1, 2}, {1, 3}};
	int l[] = {1, 2, 4};
	cout << best_path(4, 3, h, l) << '\n';
	int h2[][2] = {{0, 1}, {1, 2}};
	int l2[] = {1, 1};
	cout << best_path(3, 3, h2, l2) << '\n';
	int h3[][2] = {{0, 1}, {0, 2}, {2, 3}, {3, 4}, {4, 5}, {0, 6}, {6, 7}, {6, 8}, {8, 9}, {8, 10}};
	int l3[] = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
	cout << best_path(11, 12, h3, l3) << '\n';
	return 0;
}*/

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