Submission #384096

#	Time	Username	Problem	Language	Result	Execution time	Memory
384096		peuch	Race (IOI11_race)	C++17	0 / 100	7 ms	9708 KiB

race

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

const int MAXN = 200010; 
const int MAXA = 1000010;
const int INF = 1e8;

int n, k;

vector<int> ar[MAXN];
vector<int> wg[MAXN];

int tam;
int sub[MAXN];
int marc[MAXN];
int minProf[MAXA];

int ans;

void centDecomp(int cur);
void preCalc(int cur, int pai);
int getCent(int cur, int pai);
void getAns(int cur, int pai, int prof, int dist);
void addProf(int cur, int pai, int prof, int dist);
void removeProf(int cur, int pai, int dist);

int best_path(int N, int K, int H[][2], int L[]){
	n = N;
	k = K;
	for(int i = 0; i < n - 1; i++){
		ar[H[i][0]].push_back(H[i][1]);
		ar[H[i][1]].push_back(H[i][0]);
		wg[H[i][0]].push_back(L[i]);
		wg[H[i][1]].push_back(L[i]);
	}
	for(int i = 0; i <= k; i++)
		minProf[i] = INF;
	ans = INF;
	centDecomp(1);
	if(ans >= INF) ans = -1;
	return ans;
}

void centDecomp(int cur){
	tam = 0;
	preCalc(cur, cur);
	int cent = getCent(cur, cur);
	marc[cent] = 1;
	minProf[0] = 0;
	for(int i = 0; i < (int)ar[cent].size(); i++){
		int viz = ar[cent][i];
		if(marc[viz]) continue;
		getAns(viz, cent, 1, wg[cent][i]);
		addProf(viz, cent, 1, wg[cent][i]);
	}
	removeProf(cent, cent, 0);
}

void preCalc(int cur, int pai){
	tam++;
	sub[cur] = 1;
	for(int i = 0; i < (int)ar[cur].size(); i++){
		int viz = ar[cur][i];
		if(viz == pai || marc[viz]) continue;
		preCalc(viz, cur);
		sub[cur] += sub[viz];
	}
}

int getCent(int cur, int pai){
	for(int i = 0; i < (int)ar[cur].size(); i++){
		int viz = ar[cur][i];
		if(viz == pai || marc[viz] || sub[viz] < tam / 2) continue;
		return getCent(viz, cur);
	}
	return cur;
}

void getAns(int cur, int pai, int prof, int dist){
	dist = min(dist, INF);
	if(dist <= k) ans = min(ans, minProf[k - dist] + prof);
	for(int i = 0; i < (int)ar[cur].size(); i++){
		int viz = ar[cur][i];
		if(viz == pai || marc[viz]) continue;
		getAns(viz, cur, prof + 1, dist + wg[cur][i]);
	}
}

void addProf(int cur, int pai, int prof, int dist){
	dist = min(dist, INF);
	if(dist <= k) minProf[dist] = min(minProf[dist], prof);
	for(int i = 0; i < (int)ar[cur].size(); i++){
		int viz = ar[cur][i];
		if(viz == pai || marc[viz]) continue;
		addProf(viz, cur, prof + 1, dist + wg[cur][i]);
	}
}

void removeProf(int cur, int pai, int dist){
	dist = min(dist, INF);
	if(dist <= k) minProf[dist] = INF;
	for(int i = 0; i < (int)ar[cur].size(); i++){
		int viz = ar[cur][i];
		if(viz == pai || marc[viz]) continue;
		removeProf(viz, cur, dist + wg[cur][i]);
	}
}

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