Submission #600274

#	Time	Username	Problem	Language	Result	Execution time	Memory
600274		acatmeowmeow	Race (IOI11_race)	C++11	100 / 100	1772 ms	59016 KiB

race

//#include "race.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long 

const int NMAX = 2e5 + 5;
vector<pair<int, int>> adj[NMAX];
int sz[NMAX], dist[NMAX], depth[NMAX], ans = 1e18;
bool removed[NMAX];

int get_size(int u, int e) {
	sz[u] = 1;
	for (auto&x : adj[u]) {
		int v = x.first;
		if (v == e || removed[v]) continue;
		sz[u] += get_size(v, u);
	}
	return sz[u];
}

int get_centroid(int u, int e, int s) {
	for (auto&x : adj[u]) {
		int v = x.first;
		if (v == e || removed[v] || sz[v] <= s/2) continue;
		return get_centroid(v, u, s);
	}
	return u;
}

void dfs(int u, int e, map<int, int>&res) {
	if (!res.count(dist[u])) res[dist[u]] = depth[u];
	else res[dist[u]] = min(res[dist[u]], depth[u]);
	for (auto&x : adj[u]) {
		int v = x.first, cost = x.second;
		if (v == e || removed[v]) continue;
		dist[v] = dist[u] + cost, depth[v] = depth[u] + 1;
		dfs(v, u, res);
	}
}

void build(int u, int e, int K) {
	int s = get_size(u, e), centroid = get_centroid(u, e, s);
	map<int, int> total;
	total[0] = dist[centroid] = depth[centroid] = 0;
	for (auto&x : adj[centroid]) {
		int v = x.first, cost = x.second;
		if (v == e || removed[v]) continue;
		dist[v] = dist[centroid] + cost, depth[v] = depth[centroid] + 1;
		map<int, int> res;
		dfs(v, centroid, res);
		for (auto&x : res) {
			int cost = x.first, edge = x.second;
			if (total.count(K - cost)) ans = min(ans, edge + total[K - cost]);
		}
		for (auto&x : res) {
			int cost = x.first, edge = x.second;
			if (!total.count(cost)) total[cost] = edge;
			else total[cost] = min(total[cost], edge); 
		}
	}
	removed[centroid] = true;
	for (auto&x : adj[centroid]) {
		int v = x.first;
		if (v == e || removed[v]) continue;
		build(v, centroid, K);
	}
}

signed best_path(signed N, signed K, signed H[][2], signed L[]) {
	for (int i = 0; i < N - 1; i++) {
		int u = H[i][0], v = H[i][1], c = L[i];
		adj[u].push_back({v, c}), adj[v].push_back({u, c});
	}
	build(0, -1, K);
	return ans == 1e18 ? -1 : ans;
}

/*signed N, K, H[NMAX][2], L[NMAX];

signed main() {
	cin >> N >> K;
	for (int i = 0; i < N - 1; i++) cin >> H[i][0] >> H[i][1] >> L[i];
	cout << best_path(N, K, H, L) << '\n'; 
	return 0;
}*/

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