Submission #378464

#	Time	Username	Problem	Language	Result	Execution time	Memory
378464		rainboy	Fireworks (APIO16_fireworks)	C11	100 / 100	515 ms	18680 KiB

fireworks

#include <stdio.h>

#define N	300000

int tt[(1 + N * 2) * 2], hh[(1 + N * 2) * 2]; long long kk[1 + N * 2];

int node(long long k) {
	static int _ = 1;

	kk[_] = k;
	return _++;
}

void pul(int u) {
	int tmp;

	if (hh[tt[u << 1 | 0]] < hh[tt[u << 1 | 1]])
		tmp = tt[u << 1 | 0], tt[u << 1 | 0] = tt[u << 1 | 1], tt[u << 1 | 1] = tmp;
	hh[u] = hh[tt[u << 1 | 1]] + 1;
}

int merge(int u, int v) {
	int tmp;

	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (kk[u] < kk[v])
		tmp = u, u = v, v = tmp;
	tt[u << 1 | 1] = merge(tt[u << 1 | 1], v), pul(u);
	return u;
}

int remove_first(int u) {
	int t = merge(tt[u << 1 | 0], tt[u << 1 | 1]);

	tt[u << 1 | 0] = tt[u << 1 | 1] = 0;
	return t;
}

int main() {
	static int pp[N], cc[N], tt[N], cnt[N];
	static long long dp[N];
	int n, m, n_, i, t;
	long long ans;

	scanf("%d%d", &n, &m), n_ = n + m;
	for (i = 1; i < n_; i++)
		scanf("%d%d", &pp[i], &cc[i]), pp[i]--;
	for (i = n_ - 1; i > 0; i--) {
		dp[i] += cc[i];
		if (i >= n)
			tt[i] = merge(node(cc[i]), node(cc[i]));
		else {
			int u;

			t = tt[i];
			while (--cnt[i])
				t = remove_first(t);
			u = t, t = remove_first(t);
			kk[u] += cc[i], kk[t] += cc[i];
			tt[i] = merge(t, u);
		}
		dp[pp[i]] += dp[i], tt[pp[i]] = merge(tt[pp[i]], tt[i]), cnt[pp[i]]++;
	}
	t = tt[0];
	while (cnt[0]--)
		t = remove_first(t);
	ans = dp[0];
	while (t)
		ans -= kk[t], t = remove_first(t);
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

fireworks.c: In function 'main':
fireworks.c:48:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   48 |  scanf("%d%d", &n, &m), n_ = n + m;
      |  ^~~~~~~~~~~~~~~~~~~~~
fireworks.c:50:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   50 |   scanf("%d%d", &pp[i], &cc[i]), pp[i]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45