Submission #1013565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013565		rainboy	Jobs (BOI24_jobs)	C11	100 / 100	201 ms	52052 KiB

Main

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

#define N	300000
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(N + 1))) */

int pp[N + 1], *ej[N + 1], eo[N + 1]; long long xx[N + 1], yy[N + 1];

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 ta[N + 1], tb[N + 1];

void dfs1(int i) {
	static int t_;
	int o;

	ta[i] = t_++;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs1(j);
	}
	tb[i] = t_;
}

int st[N_ * 2], n_;

int min_(int i, int j) { return j == -1 || i != -1 && xx[i] < xx[j] ? i : j; }

void pul(int i) {
	st[i] = min_(st[i << 1 | 0], st[i << 1 | 1]);
}

void update(int i, int i_) {
	st[i += n_] = i_;
	while (i > 1)
		pul(i >>= 1);
}

int query(int l, int r) {
	int i_ = -1;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			i_ = min_(i_, st[l++]);
		if ((r & 1) == 0)
			i_ = min_(i_, st[r--]);
	}
	return i_;
}

void dfs2(int i) {
	int o;

	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs2(j);
	}
	if (yy[i] < 0)
		xx[i] = -yy[i], yy[i] = 0;
	while (1) {
		int j = query(ta[i], tb[i]);

		if (yy[i] <= xx[i]) {
			if (j == -1)
				break;
			update(ta[j], -1);
			if (yy[i] >= xx[j])
				yy[i] += yy[j] - xx[j];
			else
				xx[i] += xx[j] - yy[i], yy[i] = yy[j];
		} else {
			if (j == -1 || yy[i] < xx[j]) {
				update(ta[i], i);
				break;
			}
			update(ta[j], -1);
			yy[i] += yy[j] - xx[j];
		}
	}
}

int main() {
	int n, i, j;
	long long y;

	scanf("%d%lld", &n, &y);
	for (i = 0; i <= n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	yy[0] = y;
	for (j = 1; j <= n; j++) {
		scanf("%lld%d", &yy[j], &i);
		append(i, j);
	}
	dfs1(0);
	n_ = 1;
	while (n_ <= n)
		n_ <<= 1;
	memset(st, -1, n_ * 2 * sizeof *st);
	dfs2(0);
	printf("%lld\n", yy[0] - y);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'append':
Main.c:13:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   13 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'min_':
Main.c:35:52: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 | int min_(int i, int j) { return j == -1 || i != -1 && xx[i] < xx[j] ? i : j; }
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~
Main.c: In function 'main':
Main.c:95:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |  scanf("%d%lld", &n, &y);
      |  ^~~~~~~~~~~~~~~~~~~~~~~
Main.c:100:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |   scanf("%lld%d", &yy[j], &i);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31