Submission #679993

#	Time	Username	Problem	Language	Result	Execution time	Memory
679993		rainboy	Bitaro’s Party (JOI18_bitaro)	C11	100 / 100	905 ms	256536 KiB

bitaro

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	100000
#define K	316	/* K = floor(log2(N)) */

int max(int a, int b) { return a > b ? a : b; }

int *ei[N], eo[N];

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

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

int main() {
	static int iii[N][K], ddd[N][K], ii_[K], dd_[K], dp[N];
	static char used[N], bad[N];
	int n, m, q, k, g, g1, g2, h, i, j, o;

	scanf("%d%d%d", &n, &m, &q);
	for (i = 0; i < n; i++)
		ei[i] = (int *) malloc(2 * sizeof *ei[i]);
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(j, i);
	}
	for (j = 0; j < n; j++) {
		memset(iii[j], -1, K * sizeof *iii[j]), memset(ddd[j], -1, K * sizeof *ddd[j]);
		for (o = eo[j]; o--; ) {
			i = ei[j][o];
			k = 0, g1 = 0, g2 = 0;
			while (k < K && (ddd[i][g1] != -1 || ddd[j][g2] != -1)) {
				while (iii[i][g1] != -1 && used[iii[i][g1]])
					g1++;
				while (iii[j][g2] != -1 && used[iii[j][g2]])
					g2++;
				if (ddd[j][g2] == -1 || ddd[i][g1] != -1 && ddd[i][g1] + 1 > ddd[j][g2])
					ii_[k] = iii[i][g1], dd_[k] = ddd[i][g1] + 1, g1++;
				else
					ii_[k] = iii[j][g2], dd_[k] = ddd[j][g2], g2++;
				used[ii_[k]] = 1, k++;
			}
			for (g = 0; g < k; g++)
				used[ii_[g]] = 0;
			memcpy(iii[j], ii_, k * sizeof *ii_), memcpy(ddd[j], dd_, k * sizeof *dd_);
		}
		for (g = 0; g < K; g++)
			if (ddd[j][g] == -1) {
				iii[j][g] = j, ddd[j][g] = 0;
				break;
			}
	}
	while (q--) {
		static int ii[N];
		int v;

		scanf("%d%d", &v, &k), v--;
		for (h = 0; h < k; h++) {
			scanf("%d", &i), i--;
			ii[h] = i;
			bad[i] = 1;
		}
		if (k < K) {
			g = 0;
			while (iii[v][g] != -1 && bad[iii[v][g]])
				g++;
			printf("%d\n", ddd[v][g]);
		} else {
			for (j = 0; j < n; j++) {
				dp[j] = bad[j] ? -1 : 0;
				for (o = eo[j]; o--; ) {
					i = ei[j][o];
					if (dp[i] != -1)
						dp[j] = max(dp[j], dp[i] + 1);
				}
			}
			printf("%d\n", dp[v]);
		}
		for (h = 0; h < k; h++) {
			i = ii[h];
			bad[i] = 0;
		}
	}
	return 0;
}

Compilation message (stderr)

bitaro.c: In function 'append':
bitaro.c:15:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   15 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
bitaro.c: In function 'main':
bitaro.c:42:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   42 |     if (ddd[j][g2] == -1 || ddd[i][g1] != -1 && ddd[i][g1] + 1 > ddd[j][g2])
      |                             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.c:25:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d%d%d", &n, &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.c:29:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
bitaro.c:62:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d%d", &v, &k), v--;
      |   ^~~~~~~~~~~~~~~~~~~~~
bitaro.c:64:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86