Submission #109753

#	Time	Username	Problem	Language	Result	Execution time	Memory
109753		Erkhemkhuu	Race (IOI11_race)	C++17	43 / 100	3056 ms	24004 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
vector <pair <int, int> > adj[200005];
unordered_map <int, int> global_path, local_path;
bool isCentroid[200005] = {false};
int subtr_size[200005], localCentroid, k, ans;
inline void SubTreeSize(int v, int p) {
	subtr_size[v] = 1;
	for(auto &it: adj[v])
		if(it.F != p && !isCentroid[it.F]) {
			SubTreeSize(it.F, v);
			subtr_size[v] += subtr_size[it.F];
		}
	return;
}
inline void traverse(int v, int p, int w, int l) {
	if(w > k) return;
	if(w == k) ans = min(ans, l);
	int temp = global_path[k - w];
	if(temp) ans = min(ans, l + temp);
	if(!local_path[w] || local_path[w] > l) local_path[w] = l;
	for(auto &it: adj[v])
		if(it.F != p && !isCentroid[it.F])
			traverse(it.F, v, w + it.S, l + 1);
	return;
}
inline void findCentroid(int v, int p, int size) {
	bool flag = (size - subtr_size[v] <= size / 2);
	for(auto &it: adj[v])
		if(it.F != p && !isCentroid[it.F]) {
			flag &= (subtr_size[it.F] <= size / 2);
			findCentroid(it.F, v, size);
		}
	if(flag) localCentroid = v;
	return;
}
inline void go(int v) {
	SubTreeSize(v, -1);
	findCentroid(v, -1, subtr_size[v]);
	global_path.clear();
	isCentroid[localCentroid] = true;
	for(auto &it: adj[localCentroid])
		if(!isCentroid[it.F]) {
        	local_path.clear();
        	traverse(it.F, localCentroid, it.S, 1);
        	for(auto &localit: local_path)
        		if(!global_path[localit.F] || global_path[localit.F] > localit.S)
        			global_path[localit.F] = localit.S;
        }
	for(auto &it: adj[localCentroid])
		if(!isCentroid[it.F])
			go(it.F);
	return;
}
int best_path(int N, int K, int H[][2], int L[]) {
	int i;
	k = K;
	for(i = 0; i < N - 1; i++) {
		adj[H[i][0]].pb(mp(H[i][1], L[i]));
		adj[H[i][1]].pb(mp(H[i][0], L[i]));
	}
	ans = 1e9;
	go(0);
	if(ans == 1e9) ans = -1;
	return ans;
}

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