Submission #471199

#	Time	Username	Problem	Language	Result	Execution time	Memory
471199		hoaphat1	Race (IOI11_race)	C++17	100 / 100	646 ms	101932 KiB

race

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

int best_path(int n, int k, int edges[][2], int w[]) {
	vector<vector<pair<int, int>>> g(n);
	for (int i = 0; i < n - 1; i++) {
		g[edges[i][0]].emplace_back(edges[i][1], w[i]);
		g[edges[i][1]].emplace_back(edges[i][0], w[i]);
	}
	int ans = (int) 1e9;
	vector<map<long long, int>> s(n);
	vector<pair<long long, int>> offset(n);
	function<void(int, int)> dfs = [&](int v, int p) {
		s[v][0] = 0;
		for (auto&x : g[v]) {
			int u = x.first;
			if (u == p) continue;
			dfs(u, v);
			offset[u].first += x.second;
			offset[u].second++;
			if ((int) s[v].size() < (int) s[u].size()) {
				swap(s[v], s[u]);
				swap(offset[v], offset[u]);
			}
			for (auto& now : s[u]) {
				auto it = s[v].find(k - now.first - offset[v].first - offset[u].first);
				if (it != s[v].end()) {
					ans = min(ans, it->second + now.second + offset[v].second + offset[u].second);
				}
			}
			for (auto& now : s[u]) {
				int need = now.first + offset[u].first - offset[v].first;
				if (!s[v].count(need)) s[v][need] = (int) 1e9;
				s[v][need] = min(s[v][need], now.second + offset[u].second - offset[v].second);
			}
		}
	};
	dfs(0, -1);
	if (ans == (int) 1e9) ans = -1;
	return ans;
}
 /*
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << best_path(3, 3, {{0, 1}, {1, 2}}, {1, 1});
}*/

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