Submission #545931

#	Time	Username	Problem	Language	Result	Execution time	Memory
545931		rainboy	Magic Tree (CEOI19_magictree)	C11	100 / 100	220 ms	29168 KiB

magictree

#include <stdio.h>

#define N	100000
#define L	17	/* L = ceil(log2(100000)) */
#define N_	(N * (L + 1))

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

int ll[1 + N_], rr[1 + N_], _; long long sum[1 + N_];

int update(int t, int l, int r, int i, int x) {
	int m;

	if (t == 0)
		t = ++_;
	sum[t] += x;
	if (r - l > 1) {
		m = (l + r) / 2;
		if (i < m)
			ll[t] = update(ll[t], l, m, i, x);
		else
			rr[t] = update(rr[t], m, r, i, x);
	}
	return t;
}

int x;

int update_(int t, int l, int r, int i) {
	int m;

	if (r <= i || t == 0)
		return t;
	if (l >= i && x >= sum[t]) {
		x -= sum[t];
		return 0;
	}
	if (r - l == 1) {
		if (x >= sum[t]) {
			x -= sum[t];
			return 0;
		} else {
			sum[t] -= x, x = 0;
			return t;
		}
	}
	m = (l + r) / 2;
	ll[t] = update_(ll[t], l, m, i);
	if (x > 0)
		rr[t] = update_(rr[t], m, r, i);
	if ((sum[t] = sum[ll[t]] + sum[rr[t]]) == 0)
		t = 0;
	return t;
}

int merge(int t1, int t2) {
	if (t1 == 0)
		return t2;
	if (t2 == 0)
		return t1;
	sum[t1] += sum[t2], ll[t1] = merge(ll[t1], ll[t2]), rr[t1] = merge(rr[t1], rr[t2]);
	return t1;
}

int main() {
	static int pp[N], hh[N], ww[N], tt[N];
	int n, m, k, i;

	scanf("%d%d%d", &n, &m, &k);
	for (i = 1; i < n; i++)
		scanf("%d", &pp[i]), pp[i]--;
	while (m--) {
		int h, w;

		scanf("%d%d%d", &i, &h, &w), i--, h--;
		hh[i] = h, ww[i] = w;
	}
	for (i = n - 1; i > 0; i--) {
		if (ww[i]) {
			tt[i] = update(tt[i], 0, k, hh[i], ww[i]);
			x = ww[i], tt[i] = update_(tt[i], 0, k, hh[i] + 1);
		}
		tt[pp[i]] = merge(tt[pp[i]], tt[i]);
	}
	printf("%lld\n", sum[tt[0]]);
	return 0;
}

Compilation message (stderr)

magictree.c: In function 'main':
magictree.c:69:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d%d%d", &n, &m, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
magictree.c:71:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%d", &pp[i]), pp[i]--;
      |   ^~~~~~~~~~~~~~~~~~~
magictree.c:75:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   scanf("%d%d%d", &i, &h, &w), i--, h--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17