Submission #808964

#	Time	Username	Problem	Language	Result	Execution time	Memory
808964		Tkm_algo	Race (IOI11_race)	C++17	100 / 100	374 ms	58148 KiB

race

#include "bits/stdc++.h"
#include "race.h"

using namespace std;
using ll = long long;
const int MAXN = 1e6 + 10;
vector<pair<int, int>> adj[MAXN];
vector<int> sz(MAXN);
vector<bool> removed(MAXN);
int K, ans = 1e8;
vector<int> P(MAXN, 1e9 + 7);

int subtree_size(int u, int par = -1) {
	sz[u] = 1;
	for (auto [v, q] : adj[u]) {
		if (v == par || removed[v]) {
			continue;
		}
		sz[u] += subtree_size(v, u);
	}
	return sz[u];
}

int centroid(int u, int subsz, int par = -1) {
	for (auto [v, q] : adj[u]) {
		if (v == par || removed[v]) {
			continue;
		}
		if (sz[v] * 2 > subsz) {
			return centroid(v, subsz, u);
		}
	}
	return u;
}

void dfs(int u, int par, int dpt, int W) {
	if (W > 0 && W <= K) {
		P[W] = 1e8;
	}
	if (K > W) {
		P[K - W] = 1e8;
	}
	for (auto [v, q] : adj[u]) {
		if (v == par || removed[v]) {
			continue;
		}
		dfs(v, u, dpt + 1, W + q);
	}
}

void dfs0(int u, int par, int dpt, int W) {
	// cout << par << "--->" << u << ' ' << dpt << ' ' << W << '\n';
	if (K >= W && par != -1) {
		// cout << par << ' ' << u << ' ' << P[K - W] << ' ' << dpt << '\n';
		ans = min(ans, P[K - W] + dpt);
	}
	for (auto [v, q] : adj[u]) {
		if (v == par || removed[v]) {
			continue;
		}
		dfs0(v, u, dpt + 1, W + q);
	}
}

void dfs1(int u, int par, int dpt, int W) {
	if (K >= W && par != -1) {
		P[W] = min(P[W], dpt);
	}
	for (auto [v, q] : adj[u]) {
		if (v == par || removed[v]) {
			continue;
		}
		dfs1(v, u, dpt + 1, W + q);
	}
}

void build(int u = 0) {
	int c = centroid(u, subtree_size(u));
	// cout << c << ' ';
	removed[c] = 1;
	for (auto [v, q] : adj[c]) {
		if (removed[v]) {
			continue;
		}
		dfs(v, c, 1, q);
	}
	for (auto [v, q] : adj[c]) {
		if (removed[v]) {
			continue;
		}
		dfs0(v, c, 1, q);
		dfs1(v, c, 1, q);
	}
	for (auto [v, q] : adj[c]) {
		if (removed[v]) {
			continue;
		}
		build(v);
	}
}

int best_path(int n, int k, int h[][2], int l[]) {
	for (int i = 0; i < n - 1; i++) {
		adj[h[i][0]].push_back({h[i][1], l[i]});
		adj[h[i][1]].push_back({h[i][0], l[i]});
	}
	K = k;
	P[0] = 0;
	build();
	if (ans > n) {
		return -1;
	}
	return ans;
}

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