Submission #544721

#	Time	Username	Problem	Language	Result	Execution time	Memory
544721		rainboy	File Paths (BOI15_fil)	C11	100 / 100	105 ms	5588 KiB

fil

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

#define N	3000
#define M	3000
#define L	1000000

int *ej[N + 1], eo[N + 1], *eh[N + 1], eo_[N + 1];

void link(int **ex, int *eo, int i, int x) {
	int o = eo[i]++;

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

int dd[N + 1], pp[N + 1], ll[M]; char ans[M];
char used[L + 1]; int kk[L + 1], l_, l1;

void dfs_(int r, int i, int sign) {
	int o;

	if (dd[i] - dd[r] + l1 <= l_)
		kk[dd[i] - dd[r] + l1] += sign;
	for (o = 0; o < eo[i]; o++) {
		int j = ej[i][o];

		dfs_(r, j, sign);
	}
}

void dfs(int i) {
	int o, p;

	dfs_(i, i, 1);
	for (o = 0; o < eo_[i]; o++) {
		int h = eh[i][o], a, b;

		if (dd[i] == l_ - ll[h]) {
			ans[h] = 1;
			continue;
		}
		for (p = i; p != -1 && dd[i] - dd[p] <= l_ - ll[h]; p = pp[p]) {
			b = l_ - ll[h] - (dd[i] - dd[p]);
			if (l1 <= b && used[b - l1]) {
				ans[h] = 1;
				break;
			}
		}
		if (ans[h])
			continue;
		b = l_ - ll[h] - dd[i];
		if (b > 0)
			for (a = 1; a <= b / a; a++)
				if (b % a == 0 && (kk[a] > 0 || kk[b / a] > 0)) {
					ans[h] = 1;
					break;
				}
	}
	for (o = 0; o < eo[i]; o++) {
		int j = ej[i][o];

		dfs(j);
	}
	dfs_(i, i, -1);
}

int main() {
	int n, m, h, i;

	scanf("%d%d%d%d", &n, &m, &l_, &l1), l1++;
	for (i = 0; i <= n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	}
	pp[0] = -1;
	for (i = 1; i <= n; i++) {
		scanf("%d%d", &pp[i], &dd[i]), dd[i] += dd[pp[i]] + 1;
		link(ej, eo, pp[i], i);
	}
	for (i = 0; i <= n; i++)
		if (dd[i] <= l_)
			used[dd[i]] = 1;
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &ll[h]), ll[h]++;
		link(eh, eo_, i, h);
	}
	dfs(0);
	for (h = 0; h < m; h++)
		printf(ans[h] ? "YES\n" : "NO\n");
	return 0;
}

Compilation message (stderr)

fil.c: In function 'link':
fil.c:13:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   13 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
fil.c: In function 'main':
fil.c:72:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  scanf("%d%d%d%d", &n, &m, &l_, &l1), l1++;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.c:79:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   scanf("%d%d", &pp[i], &dd[i]), dd[i] += dd[pp[i]] + 1;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fil.c:86:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   scanf("%d%d", &i, &ll[h]), ll[h]++;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 33 / 33
• Subtask 3: 34 / 34