Submission #402334

#	Time	Username	Problem	Language	Result	Execution time	Memory
402334		rainboy	Race (IOI11_race)	C11	100 / 100	799 ms	37660 KiB

race

#include "race.h"
#include <stdlib.h>
#include <string.h>

#define N	200000
#define L	1000000
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

int ij[N - 1], ww[N - 1];
int *eh[N], eo[N];

void append(int i, int h) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}

int sz[N], c;

void dfs0(int p, int i, int n) {
	int o, centroid;

	sz[i] = 1, centroid = 1;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ij[h];

		if (j != p) {
			dfs0(i, j, n);
			if (sz[j] * 2 > n)
				centroid = 0;
			sz[i] += sz[j];
		}
	}
	if ((n - sz[i]) * 2 > n)
		centroid = 0;
	if (centroid)
		c = i;
}

int xx[N], dd[N], dd_[L + 1], qu[N], l, cnt, ans;

void dfs1(int p, int i, int x, int d) {
	int o;

	xx[i] = x, dd[i] = d;
	if (x <= l)
		ans = min(ans, dd_[l - x] + d);
	qu[cnt++] = i;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ij[h];

		if (j != p)
			dfs1(i, j, min(x + ww[h], l + 1), d + 1);
	}
}

void delete(int i, int h) {
	int o;

	for (o = eo[i]; o--; )
		if (eh[i][o] == h) {
			eo[i]--;
			while (o < eo[i])
				eh[i][o] = eh[i][o + 1], o++;
			return;
		}
}

void cd(int i, int n) {
	int o, g;

	dfs0(-1, i, n), i = c;
	cnt = 0;
	xx[i] = 0, dd[i] = 0;
	qu[cnt++] = i, dd_[xx[i]] = dd[i];
	for (o = eo[i], g = 0; o--; ) {
		int h = eh[i][o], j = i ^ ij[h];

		delete(j, h);
		dfs1(i, j, min(ww[h], l + 1), 1);
		while (g < cnt) {
			j = qu[g++];
			if (xx[j] <= l)
				dd_[xx[j]] = min(dd_[xx[j]], dd[j]);
		}
	}
	while (cnt--) {
		int j = qu[cnt];

		if (xx[j] <= l)
			dd_[xx[j]] = INF;
	}
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ij[h];

		cd(j, sz[j] < sz[i] ? sz[j] : n - sz[i]);
	}
}

int best_path(int n, int l_, int ii_[][2], int *ww_) {
	int h, i, j;

	memcpy(ww, ww_, (n - 1) * sizeof *ww_), l = l_;
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < n - 1; h++) {
		i = ii_[h][0], j = ii_[h][1];
		ij[h] = i ^ j;
		append(i, h), append(j, h);
	}
	memset(dd_, 0x3f, (l + 1) * sizeof *dd_);
	ans = INF;
	cd(0, n);
	if (ans == INF)
		ans = -1;
	return ans;
}

Compilation message (stderr)

race.c: In function 'append':
race.c:17:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   17 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

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