oj.uz

답안 #402503

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402503 2021-05-11T19:28:03 Z rainboy 열대 식물원 (Tropical Garden) (IOI11_garden) C
100 / 100
 200 ms 37188 KB 
/* 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

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.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 3 ms 548 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 3 ms 548 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 18 ms 4684 KB Output is correct
12 Correct 42 ms 7324 KB Output is correct
13 Correct 68 ms 28016 KB Output is correct
14 Correct 174 ms 23820 KB Output is correct
15 Correct 164 ms 24088 KB Output is correct
16 Correct 122 ms 16832 KB Output is correct
17 Correct 96 ms 14148 KB Output is correct
18 Correct 37 ms 7364 KB Output is correct
19 Correct 162 ms 24516 KB Output is correct
20 Correct 166 ms 24724 KB Output is correct
21 Correct 115 ms 17292 KB Output is correct
22 Correct 98 ms 14788 KB Output is correct
23 Correct 184 ms 27284 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 3 ms 548 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 18 ms 4684 KB Output is correct
12 Correct 42 ms 7324 KB Output is correct
13 Correct 68 ms 28016 KB Output is correct
14 Correct 174 ms 23820 KB Output is correct
15 Correct 164 ms 24088 KB Output is correct
16 Correct 122 ms 16832 KB Output is correct
17 Correct 96 ms 14148 KB Output is correct
18 Correct 37 ms 7364 KB Output is correct
19 Correct 162 ms 24516 KB Output is correct
20 Correct 166 ms 24724 KB Output is correct
21 Correct 115 ms 17292 KB Output is correct
22 Correct 98 ms 14788 KB Output is correct
23 Correct 184 ms 27284 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 23 ms 4700 KB Output is correct
26 Correct 40 ms 7748 KB Output is correct
27 Correct 70 ms 28764 KB Output is correct
28 Correct 164 ms 24324 KB Output is correct
29 Correct 166 ms 24772 KB Output is correct
30 Correct 132 ms 17460 KB Output is correct
31 Correct 94 ms 14472 KB Output is correct
32 Correct 38 ms 7364 KB Output is correct
33 Correct 170 ms 24528 KB Output is correct
34 Correct 169 ms 24764 KB Output is correct
35 Correct 119 ms 17348 KB Output is correct
36 Correct 95 ms 14812 KB Output is correct
37 Correct 200 ms 27336 KB Output is correct
38 Correct 133 ms 37188 KB Output is correct