Submission #402366

#	Time	Username	Problem	Language	Result	Execution time	Memory
402366		rainboy	Tropical Garden (IOI11_garden)	C11	69 / 100	5066 ms	45852 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <stdlib.h>

#define N	150000
#define M	150000
#define L	29	/* L = floor(log2(10^9)) */
#define INF	0x3f3f3f3f

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 pp[L + 1][M * 2];

int get(int i, int k) {
	int l;

	for (l = L; l >= 0; l--)
		if (k >= 1 << l)
			i = pp[l][i], k -= 1 << l;
	return i;
}

void count_routes(int n, int m, int p, int ii[][2], int q, int *kk) {
	static int hh[N];
	static char good[M * 2];
	int h, i, l, o;

	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < m; h++)
		append(ii[h][0], h << 1 | 0), append(ii[h][1], h << 1 | 1);
	for (i = 0; i < n; i++) {
		int h1, h2;

		h1 = INF, h2 = INF;
		for (o = eo[i]; o--; ) {
			h = eh[i][o];
			if (h1 > h)
				h2 = h1, h1 = h;
			else if (h2 > h)
				h2 = h;
		}
		hh[i] = h1;
		if (h2 == INF)
			pp[0][h1 ^ 1] = h1;
		else {
			pp[0][h1 ^ 1] = h2;
			for (o = eo[i]; o--; ) {
				h = eh[i][o];
				if (h != h1)
					pp[0][h ^ 1] = h1;
			}
		}
	}
	for (o = eo[p]; o--; ) {
		h = eh[p][o];
		good[h ^ 1] = 1;
	}
	for (l = 1; l <= L; l++)
		for (h = 0; h < m * 2; h++)
			pp[l][h] = pp[l - 1][pp[l - 1][h]];
	for (h = 0; h < q; h++) {
		int k = kk[h] - 1, cnt;

		cnt = 0;
		for (i = 0; i < n; i++)
			if (good[get(hh[i], k)])
				cnt++;
		answer(cnt);
	}
}

Compilation message (stderr)

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

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31