Submission #703628

#	Time	Username	Problem	Language	Result	Execution time	Memory
703628		boyliguanhan	Race (IOI11_race)	C++17	31 / 100	299 ms	37164 KiB

race

#include "race.h"
#include<vector>
#include<utility>
#include<map>
#include<algorithm>
using namespace std;
#define int long long
#define inf 1000000000
vector<pair<int, int>> adj[200100];
int ans = inf, rt, k, sz[200100];
bool vis[200100];
map<int, int> cache;
void csz(int n, int p, int tot) {
	int ms = 0;
	sz[n] = 1;
	for (auto &i : adj[n])
		if (i.first != p && !vis[i.first])
			csz(i.first, n, tot), ms = max(ms, sz[i.first]), sz[n] += sz[i.first];
	if (ms <= tot / 2 && sz[n] >= tot / 2)
		rt = n;
}
void cans(int n, int p, int d1, int d2) {
	if (d1 > k)
		return;
	if (cache.count(k - d1))
		ans = min(ans, d2 + cache[k - d1]);
	for (auto &i : adj[n])
		if (i.first != p && !vis[i.first])
			cans(i.first, n, d1 + i.second, d2 + 1);
}
void ccache(int n, int p, int d1, int d2) {
	if (d1 > k)
		return;
	if (cache.count(d1))
		cache[d1] = min(cache[d1], d2);
	else
		cache[d1] = d2;
	for (auto& i : adj[n])
		if (i.first != p && !vis[i.first])
			ccache(i.first, n, d1 + i.second, d2 + 1);
}
void decomp(int n, int tot) {
	vector<int> v;
	cache.clear();
	cache[0];
	csz(n, -1, tot);
	n = rt;
	vis[n] = 1;
	for (auto &i : adj[n]) {
		if (!vis[i.first])
			cans(i.first, -1, i.second, 1), ccache(i.first, -1, i.second, 1);
		v.push_back(sz[i.first]);
	}
	int x = 0;
	for (auto &i : adj[n]) {
		if (!vis[i.first])
			decomp(i.first, v[x]);
		x++;
	}
}
signed best_path(signed N, signed K, signed H[][2], signed 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;
	decomp(0, N);
	return ans == inf ? -1 : ans;
}

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