제출 #402415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
402415		rainboy	열대 식물원 (Tropical Garden) (IOI11_garden)	C11	100 / 100	2954 ms	25080 KiB

garden

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

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

void append(int **eh, int *eo, 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 *eh[N], eo[N], *fj[M * 2], fo[M * 2];
int qu1[M * 2], cnt1, qu2[M * 2], cnt2; char src[M * 2], dest[M * 2], visited[M * 2];
int kk[Q], ans[Q], q;

void dfs(int i, int r) {
	int o, h;

	visited[i] = 1;
	qu2[cnt2++] = i;
	if (src[i])
		for (h = 0; h < q; h++) {
			int p = kk[h] < cnt2 ? qu2[cnt2 - 1 - kk[h]] : qu1[(r + kk[h] - (cnt2 - 1)) % cnt1];

			if (dest[p])
				ans[h]++;
		}
	for (o = fo[i]; o--; ) {
		int j = fj[i][o];

		if (visited[j] != 1)
			dfs(j, r);
	}
	cnt2--;
}

void count_routes(int n, int m, int p, int ii[][2], int q_, int *kk_) {
	static int pp[M * 2];
	int h, i, j, o;

	q = q_;
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < m; h++)
		append(eh, eo, ii[h][0], h << 1 | 0), append(eh, eo, 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;
		}
		src[h1] = 1;
		if (h2 == INF)
			pp[h1 ^ 1] = h1;
		else {
			pp[h1 ^ 1] = h2;
			for (o = eo[i]; o--; ) {
				h = eh[i][o];
				if (h != h1)
					pp[h ^ 1] = h1;
			}
		}
	}
	for (o = eo[p]; o--; ) {
		h = eh[p][o];
		dest[h ^ 1] = 1;
	}
	for (h = 0; h < q; h++)
		kk[h] = kk_[h] - 1;
	for (i = 0; i < m * 2; i++)
		fj[i] = (int *) malloc(2 * sizeof *fj[i]);
	for (i = 0; i < m * 2; i++)
		append(fj, fo, pp[i], i);
	for (i = 0; i < m * 2; i++)
		if (!visited[i]) {
			j = i;
			while (!visited[j])
				visited[j] = -1, j = pp[j];
			cnt1 = 0;
			while (visited[j] == -1) {
				visited[j] = 1, j = pp[j];
				qu1[cnt1++] = j;
			}
			cnt2 = 0;
			for (h = 0; h < cnt1; h++)
				dfs(qu1[h], h);
		}
	for (h = 0; h < q; h++)
		answer(ans[h]);
}

컴파일 시 표준 에러 (stderr) 메시지

garden.c: In function 'append':
garden.c:14:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
garden.c: In function 'count_routes':
garden.c:64:11: warning: writing 1 byte into a region of size 0 [-Wstringop-overflow=]
   64 |   src[h1] = 1;
      |   ~~~~~~~~^~~
garden.c:20:46: note: at offset 1061109567 to object 'src' with size 300000 declared here
   20 | int qu1[M * 2], cnt1, qu2[M * 2], cnt2; char src[M * 2], dest[M * 2], visited[M * 2];
      |                                              ^~~

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