Submission #854777

#	Time	Username	Problem	Language	Result	Execution time	Memory
854777		alex_2008	Race (IOI11_race)	C++17	100 / 100	603 ms	60176 KiB

race

#include "race.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <unordered_map>
#include <cassert>
using namespace std;
const int MAX_N = 5e5 + 10;
bool used[MAX_N];
int subtree[MAX_N], dist[MAX_N], height[MAX_N];
int h[MAX_N][2], l[MAX_N];
int KK;
int ans = MAX_N;
vector <vector<pair<int, int>>> G;
int find_centroid(int v) {
	int p = -1;
	int u = v;
	while (1) {
		int x = -1;
		for (auto it : G[u]) {
			if (it.first == p) continue;
			if (used[it.first]) continue;
			if (2 * subtree[it.first] > subtree[v]) {
				x = it.first;
				break;
			}
		}
		if (x == -1) return u;
		p = u;
	    u = x;
	}
}
void dfs(int v, int p) {
	if (p == -1) {
		dist[v] = 0;
		height[v] = 0;
	}
	subtree[v] = 1;
	for (auto it : G[v]) {
		if (it.first == p || used[it.first]) continue;
		dist[it.first] = min(dist[v] + it.second, KK + 1);
		height[it.first] = height[v] + 1;
		dfs(it.first, v);
		subtree[v] += subtree[it.first];
	}
}
vector <int> vec;
void find_vertexes(int v, int p) {
	vec.push_back(v);
	for (auto it : G[v]) {
		if (used[it.first] || it.first == p) continue;
		find_vertexes(it.first, v);
	}
}
void solve(int v) {
	dfs(v, -1);
	v = find_centroid(v);
	dfs(v, -1);
	vector <vector<int>> u;
	for (auto it : G[v]) {
		if (used[it.first]) continue;
		vec.clear();
		find_vertexes(it.first, v);
		u.push_back(vec);
	}
	unordered_map <int, int> mp;
	for (auto it : u) {
		for (auto j : it) {
			if (mp.find(KK - dist[j]) != mp.end()) {
				ans = min(ans, height[j] + mp[KK - dist[j]]);
			}
		}
		for (auto j : it) {
			if (mp.find(dist[j]) == mp.end()) {
				mp[dist[j]] = height[j];
			}
			else mp[dist[j]] = min(mp[dist[j]], height[j]);
		}
	}
	if (mp.find(KK) != mp.end()) {
		ans = min(ans, mp[KK]);
	}
	used[v] = true;
	for (auto it : G[v]) {
		if (used[it.first]) continue;
		solve(it.first);
	}
}
int best_path(int N, int K, int H[][2], int L[]) {
	KK = K;
	G.resize(N);
	for (int i = 0; i < N - 1; i++) {
		G[H[i][0]].push_back({ H[i][1], L[i] });
		G[H[i][1]].push_back({ H[i][0], L[i] });
	}
	solve(0);
	if (ans == MAX_N) return -1;
	return ans;
}
//int main() {
//	int n, k;
//	cin >> n >> k;
//	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) << "\n";
//}

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