Submission #41188

#	Time	Username	Problem	Language	Result	Execution time	Memory
41188		Just_Solve_The_Problem	Race (IOI11_race)	C++11	100 / 100	916 ms	43224 KiB

race

#include <race.h>
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair < ll, ll >
#define mk make_pair
#define fr first
#define sc second
#define pb push_back
#define ok puts("ok");

const int N = (int)2e5 + 7;
const int nn = (int)1e6 + 7;

ll can[nn], mnpath[nn];
int n, k, book;
vector < pii > gr[N];
int sz[N];
bool del[N];
ll ans = -1;

void dfs(int v, int pr) {
	sz[v] = 1;
	for (auto to : gr[v]) {
		if (to.fr == pr || del[to.fr]) continue;
		dfs(to.fr, v);
		sz[v] += sz[to.fr];
	}
}

int findcentroid(int v) {
	int now = v;
	int siz = sz[v];
	int pr = -1;
	bool fl = 1;
	while (1) {
		fl = 1;
		for (auto to : gr[now]) {
			if (to.fr == pr || del[to.fr]) continue;
			if (sz[to.fr] * 2 >= siz) {
				pr = now;
				now = to.fr;
				fl = 0;
				break;
			}
		}
		if (fl) break;
	}
	return now;
}

void dfs1(int v, int pr, int curcost, int curlen, int tp) {
	if (curcost > k)
		return ;
	if (tp == 0) {
		if (can[k - curcost] == book) {
			if (curlen + mnpath[k - curcost] < ans || ans == -1) {
				ans = curlen + mnpath[k - curcost];
			}
		}
		if (curcost == k && (curlen < ans || ans == -1)) {
			ans = curlen;
		}
	} else {
		if (can[curcost] < book) {
			can[curcost] = book;
			mnpath[curcost] = curlen;
		} else if (curlen < mnpath[curcost]) {
			can[curcost] = book;
			mnpath[curcost] = curlen;
		}
	}
	for (auto to : gr[v]) {
		if (to.fr == pr || del[to.fr]) continue;
		dfs1(to.fr, v, curcost + to.sc, curlen + 1, tp);
	}
}                 

void compute(int v) {
	dfs(v, 0);
	if (sz[v] <= 1)
		return ;
	int centroid = -1;
	centroid = findcentroid(v);
	book++;
	for (auto to : gr[centroid]) {
		if (del[to.fr]) continue;
		dfs1(to.fr, centroid, to.sc, 1, 0);
		dfs1(to.fr, centroid, to.sc, 1, 1);
	}
	// printf("### %d %d\n", centroid, ans);     
	del[centroid] = 1;
	for (auto to : gr[centroid]) {
		if (del[to.fr]) continue;
		compute(to.fr);
	}
}

int best_path (int _n, int _k, int _h[][2], int _l[]) {
	n = _n; k = _k;	
	for (int i = 0; i < n - 1; i++) {
		ll u, v, w;
		u = _h[i][0] + 1; v = _h[i][1] + 1; w = _l[i];
		gr[v].pb(mk(u, w));
		gr[u].pb(mk(v, w));
	}
	compute(1);       
	return ans;
}

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