Submission #416293

#	Time	Username	Problem	Language	Result	Execution time	Memory
416293		DEQK	Race (IOI11_race)	C++17	43 / 100	399 ms	75956 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200200;
ll ans = -1;
ll d[N], K;
ll len[N];
vector<pair<int, int>> g[N];
void calc(int u,int p,ll x = 0) {
	len[u] = x;
	for(auto to : g[u]) if(to.first != p) {
		d[to.first] = d[u] + 1;
		calc(to.first, u, x + to.second);
	}
}
map<ll, ll> dfs(int u,int p) {
	map<ll, ll> own;
	own[len[u]] = d[u];
	for(auto to : g[u]) if(to.first != p) {
		auto x = dfs(to.first, u);
		if(x.size() > own.size()) {
			own.swap(x);
		}
		for(auto it : x) {
			if(own.count(K - it.first + 2 * len[u])) {
				if(ans == -1) {
					ans = own[K - it.first + 2 * len[u]] + it.second - 2 * d[u];
				} else {
					ans = min(ans, own[K - it.first + 2 * len[u]] + it.second - 2 * d[u]);
				}
			}
			if(own.count(it.first)) {
				own[it.first] = min(own[it.first], it.second);
			} else {
				own[it.first] = it.second;
			}
		}
	}
	return own;
}
int best_path(int n, int k, int h[][2], int l[]) {
	K = k;
	for(int i = 0; i < n - 1; i++) {
		ll u = h[i][0],v = h[i][1], w = l[i];
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	calc(0, -1);
	dfs(0, -1);
	return ans;
}
/*int main() {
	int n, k; cin >> n >> k;
	int h[n - 1][2], l[n - 1];
	for(int i = 0; i < n - 1; ++i) {
		cin >> h[i][0] >> h[i][1];
	}
	for(int i = 0; i < n - 1; ++i) {
		cin >> l[i];
	}
	cout << best_path(n, k, h, l);
}*/

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