Submission #1194199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194199		PlayVoltz	Race (IOI11_race)	C++20	100 / 100	359 ms	50240 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define mp make_pair
#define pb push_back

const int MAXN=2e5+5;

int n, k, ans=INT_MAX;
set<pii> graph[MAXN];
vector<pii> lazy;
int subtree[MAXN], par[MAXN], dist[1000005];
vector<int> revert;

int dfs_size(int u, int p){
	subtree[u] = 1;
	for (auto v:graph[u]){
		if (v.first==p)continue;
		subtree[u]+=dfs_size(v.first, u);
	}
	return subtree[u];
}

int centroidfind(int u, int p, int size){
	for (auto v:graph[u]){
		if (v.first!=p && subtree[v.first]>size/2)return centroidfind(v.first, u, size);
	}
	return u;
}

void check(int node, int par, int d, int e){
	if (d>k)return;
	ans=min(ans, dist[k-d]+e);
	lazy.pb(mp(d, e));
	for (auto num:graph[node])if (num.first!=par)check(num.first, node, d+num.second, e+1);
}

void build(int u, int p, int d){
	int size = dfs_size(u, p);
	int centroid = centroidfind(u, p, size);
	par[centroid] = p;
	for (auto num:revert)dist[num]=INT_MAX/2;
	revert.clear();
	dist[0]=0;
	for (auto v:graph[centroid]){
		lazy.clear();
		check(v.first, centroid, v.second, 1);
		for (auto num:lazy){
			dist[num.first]=min(dist[num.first], num.second);
			revert.pb(num.first);
		}
	}
	vector<pii> temp;
	for (auto v:graph[centroid])temp.pb(v);
	for (auto num:temp){
		graph[num.first].erase(mp(centroid, num.second));
		graph[centroid].erase(num);
		build(num.first, centroid, num.second);
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	n=N, k=K;
	for (int i=0; i<n-1; ++i){
		graph[H[i][0]].insert(mp(H[i][1], L[i]));
		graph[H[i][1]].insert(mp(H[i][0], L[i]));
	}
	for (int i=0; i<=k; ++i)dist[i]=INT_MAX/2;
	build(0, -1, 0);
	return (ans>=INT_MAX/2 ? -1:ans);
}

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