Submission #1035961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035961		andrewp	Race (IOI11_race)	C++14	0 / 100	5 ms	14428 KiB

race

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

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

#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) {
	for (auto u : g[x]) {
		if (u.first != par) {
			build(u.first, x);
			dep[u.first] = dep[x] + 1;
			price[u.first] = price[x] + u.second;
		}
	}
}

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()) {
				swap(mp[u.first], mp[x]);
			}
			int calc = 2 * price[x] + k;
			for (auto add : mp[u.first]) {
				calc -= add.first;
				if (mp[x].count(calc)) {
					ans = min(ans, mp[x][calc] + u.second - 2 * dep[x]);
				}
				calc += add.first;
			}
			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][calc - price[x]]) {
				ans = min(ans, mp[x][calc - price[x]] - dep[x]);
			}
		}
	}
}

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);
	dfs(0, -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 == INF ? -1 : ans - 1) << '\n';
// }

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