Submission #698969

#	Time	Username	Problem	Language	Result	Execution time	Memory
698969		boyliguanhan	Race (IOI11_race)	C++17	9 / 100	3060 ms	22604 KiB

race

#include "race.h"
#include<vector>
#include<utility>
#include<map>
#include<algorithm>
using namespace std;
vector<pair<int, int>> adj[100100];
int ans = 1e9, rt, k;
bool vis[100100];
void csz(vector<int>& sz, int n, int p, int tot) {
	int ms = 0;
	for (auto i : adj[n])
		if (i.first != p && !vis[i.first])
			csz(sz, 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(map<long long, int>& cache, 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(cache, i.first, n, d1 + i.second, d2 + 1);
}
void ccache(map<long long, int>& cache, 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(cache, i.first, n, d1 + i.second, d2 + 1);
}
void decomp(int n, int tot) {
	vector<int> sz(100100, 1);
	map<long long, int> cache{ {0,0} };
	csz(sz, n, -1, tot);
	vis[rt] = 1;
	for (auto i : adj[rt])
		if (!vis[i.first])
			cans(cache, i.first, -1, i.second, 1), ccache(cache, i.first, -1, i.second, 1);
	for (auto i : adj[rt])
		if (!vis[i.first])
			decomp(i.first, sz[i.first]);
}
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;
	decomp(0, N);
	return ans==1e9?-1:ans;
}

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