Submission #402503

#	Time	Username	Problem	Language	Result	Execution time	Memory
402503		rainboy	Tropical Garden (IOI11_garden)	C11	100 / 100	200 ms	37188 KiB

garden

/* https://oj.uz/submission/246701 (rqi) */
#include "garden.h"
#include "gardenlib.h"
#include <string.h>
#include <stdlib.h>

#define N	150000
#define Q	2000
#define INF	0x3f3f3f3f

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int *ej[N * 2], eo[N * 2], n;

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

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

int rr[N * 2], xx[N * 2], yy[N * 2], cc[N * 2], ta[N * 2], tb[N * 2], r, c; char state[N * 2];

void dfs(int i, int x, int y) {
	static int time;
	int o;

	if (state[i] == -2)
		state[i] = 2, x = 0;
	else
		state[i] = 1;
	rr[i] = r, xx[i] = x, yy[i] = y % c, cc[i] = c, ta[i] = time++;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (state[j] <= 0)
			dfs(j, x + 1, y + 1);
	}
	tb[i] = time;
}

int compare_xt(int i, int j) {
	return xx[i] != xx[j] ? xx[i] - xx[j] : ta[i] - ta[j];
}

int compare_ryx(int i, int j) {
	return rr[i] != rr[j] ? rr[i] - rr[j] : (yy[i] != yy[j] ? yy[i] - yy[j] : xx[i] - xx[j]);
}

void sort(int *ii, int l, int r, int (*compare)(int, int)) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i, compare);
		l = k;
	}
}

int ii[N], jj[N];

int search1(int x, int t) {
	int lower = -1, upper = n;

	while (upper - lower > 1) {
		int h = (lower + upper) / 2, i = ii[h];
		
		if (xx[i] < x || xx[i] == x && ta[i] < t)
			lower = h;
		else
			upper = h;
	}
	return lower + 1;
}

int search2(int r, int y, int x) {
	int lower = -1, upper = n;

	while (upper - lower > 1) {
		int h = (lower + upper) / 2, j = jj[h];
		
		if (rr[j] < r || rr[j] == r && (yy[j] < y || yy[j] == y && xx[j] < x))
			lower = h;
		else
			upper = h;
	}
	return lower + 1;
}

int query(int i, int k) {
	if (state[i] == 1) {
		int x = xx[i] + k;

		return search1(x, tb[i]) - search1(x, ta[i]);
	} else {
		int r = rr[i], y = (yy[i] + k) % cc[i];

		return search2(r, y, k + 1) - search2(r, y, 0);
	}
}

void count_routes(int n_, int m, int p, int ij[][2], int q, int *kk) {
	static int hh1[N], hh2[N], pp[N * 2];
	int h, i, j;

	n = n_;
	memset(hh1, -1, n * sizeof *hh1), memset(hh2, -1, n * sizeof *hh2);
	for (h = 0; h < m; h++) {
		i = ij[h][0], j = ij[h][1];
		if (hh1[i] == -1)
			hh1[i] = h;
		else if (hh2[i] == -1)
			hh2[i] = h;
		if (hh1[j] == -1)
			hh1[j] = h;
		else if (hh2[j] == -1)
			hh2[j] = h;
	}
	for (i = 0; i < n; i++) {
		h = hh1[i], j = i ^ ij[h][0] ^ ij[h][1];
		pp[i << 1 | 0] = j << 1 | (hh1[j] == h ? 1 : 0);
		h = hh2[i] == -1 ? hh1[i] : hh2[i], j = i ^ ij[h][0] ^ ij[h][1];
		pp[i << 1 | 1] = j << 1 | (hh1[j] == h ? 1 : 0);
	}
	for (i = 0; i < n * 2; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (i = 0; i < n * 2; i++)
		append(pp[i], i);
	for (i = 0; i < n * 2; i++)
		if (!state[i]) {
			for (j = i; !state[j]; j = pp[j])
				state[j] = -1;
			c = 0;
			while (state[j] == -1) {
				state[j] = -2, j = pp[j];
				c++;
			}
			r = j, dfs(j, 0, 0);
		}
	for (i = 0; i < n; i++)
		ii[i] = i << 1 | 0;
	sort(ii, 0, n, compare_xt);
	for (i = 0; i < n; i++)
		jj[i] = i << 1 | 0;
	sort(jj, 0, n, compare_ryx);
	for (h = 0; h < q; h++)
		answer(query(p << 1 | 0, kk[h]) + query(p << 1 | 1, kk[h]));
}

Compilation message (stderr)

garden.c: In function 'append':
garden.c:22:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   22 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
garden.c: In function 'search1':
garden.c:85:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   85 |   if (xx[i] < x || xx[i] == x && ta[i] < t)
      |                    ~~~~~~~~~~~^~~~~~~~~~~~
garden.c: In function 'search2':
garden.c:99:59: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   99 |   if (rr[j] < r || rr[j] == r && (yy[j] < y || yy[j] == y && xx[j] < x))
      |                                                ~~~~~~~~~~~^~~~~~~~~~~~
garden.c:99:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   99 |   if (rr[j] < r || rr[j] == r && (yy[j] < y || yy[j] == y && xx[j] < x))
      |                    ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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