Submission #1036530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036530		andrewp	Race (IOI11_race)	C++14	100 / 100	323 ms	86096 KiB

race

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

using pii = pair<int, int>;
using ll = int64_t;

//#define int ll

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << #x << ": " << x << '\n';

const int N = 2e5 + 20, INF = 1e9 + 20;
int n, price[N], dep[N];
int k, ans = INF;
vector<pii> g[N];
map<int, int> mp[N];

void build(int x, int par, int pr, int d) {
	price[x] = pr, dep[x] = d;
	for (auto u: g[x]) {
		if (u.first != par) {
			build(u.first, x, pr + u.second, d + 1);
		}
	}
}

void dfs(int x, int par) {
	mp[x][price[x]] = dep[x];
	for (auto u: g[x]) {
		if (u.first != par) {
			dfs(u.first, x);
			if (mp[u.first].size() > mp[x].size()) {
				mp[x].swap(mp[u.first]);
			}
			for (auto add: mp[u.first]) {
				int calc = 2 * price[x] + k - add.first;
				if (mp[x].count(calc)) {
					ans = min(ans, mp[x][calc] + add.second - 2 * dep[x]);
				}
			}
			for (auto add: mp[u.first]) {
				if (mp[x].count(add.first)) {
					mp[x][add.first] = min(mp[x][add.first], add.second);
				} else {
					mp[x][add.first] = add.second;
				}
			}
			if (mp[x].count(k + price[x])) {
				ans = min(ans, mp[x][k + price[x]] - dep[x]);
			}
		}
	}
	// if (x == 1) dbg(mp[x].count(2));
}

int best_path(int NN, int K, int H[][2], int LEN[]) {
	n = NN, k = K;
	for (int i = 0; i < n - 1; i++) {
		int u = H[i][0];
		int v = H[i][1];
		int w = LEN[i];
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	dep[0] = 0, price[0] = 0;
	build(0, -1, 0, 0);
	dfs(0, -1);
	if (ans == INF) ans = -1;
	return ans;
}

// int32_t main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);
// 	cout.tie(nullptr);
// 	cerr.tie(nullptr);
//
// 	int NN, K;
// 	cin >> NN >> K;
//
// 	int H[NN][2], LEN[NN];
//
// 	for (int i = 0; i < NN - 1; i++) {
// 		cin >> H[i][0] >> H[i][1];
// 	}
// 	for (int i = 0; i < NN - 1; i++) {
// 		cin >> LEN[i];
// 	}
// 	int ans = best_path(NN, K, H, LEN);
// 	cout << "Solution: " << ans << '\n';
// }

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