Submission #1278625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278625		IBory	Race (IOI11_race)	C++20	21 / 100	96 ms	18308 KiB

race

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 100007, LIM = 1000007;
int Z[MAX], V[MAX], D[LIM];
vector<pii> G[MAX];

int GetSize(int cur, int prev) {
	int& ret = Z[cur] = 1;
	for (auto [next, _] : G[cur]) {
		if (V[next] || next == prev) continue;
		ret += GetSize(next, cur);
	}
	return ret;
}

int GetCent(int cur, int prev, int lim) {
	for (auto [next, _] : G[cur]) {
		if (V[next] || next == prev) continue;
		if (Z[next] * 2 > lim) return GetCent(next, cur, lim);
	}
	return cur;
}

int ret;
vector<int> ST;
void DFS(int cur, int prev, int cnt, int cd, int K, bool upd) {
	if (upd) ret = min(ret, cnt + D[K - cd]);
	else {
		D[cd] = min(D[cd], cnt);
		ST.push_back(cd);
	}
	for (auto& [next, dist] : G[cur]) {
		if (V[next] || next == prev) continue;
		if (cd + dist <= K) DFS(next, cur, cnt + 1, cd + dist, K, upd);
	}
}

void DnC(int cur, int K) {
	int C = GetCent(cur, -1, GetSize(cur, -1));
	V[C] = 1;

	for (auto [next, dist] : G[C]) {
		if (V[next] || dist > K) continue;
		DFS(next, -1, 1, dist, K, 1);
		DFS(next, -1, 1, dist, K, 0);
	}
	ret = min(ret, D[K]);

	for (int n : ST) D[n] = 1e9;
	ST.clear();

	for (auto [next, _] : G[C]) if (!V[next]) DnC(next, K);
}

int best_path(int N, int K, int E[][2], int W[]) {
	for (int i = 0; i < N - 1; ++i) {
		int a = E[i][0] + 1, b = E[i][1] + 1;
		G[a].emplace_back(b, W[i]);
		G[b].emplace_back(a, W[i]);
	}

	ret = 1e9;
	memset(D, 0x3f, sizeof(D));
	DnC(1, K);
	return (1E9 == ret ? -1 : ret);
}

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