제출 #378472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378472		rainboy	Fireworks (APIO16_fireworks)	C11	100 / 100	713 ms	18796 KiB

fireworks

#include <stdio.h>
 
#define N	300000
 
int tt[(1 + N * 2) * 2], hh[(1 + N * 2) * 2]; char side[1 + N * 2]; long long kk[1 + N * 2];
 
int node(long long k) {
	static int _ = 1;
 
	kk[_] = k, side[_] = 1;
	return _++;
}
 
void pul(int u) {
	side[u] = hh[tt[u << 1 | 0]] > hh[tt[u << 1 | 1]], hh[u] = hh[tt[u << 1 | side[u]]] + 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 | side[u]] = merge(tt[u << 1 | side[u]], 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, pul(u);
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

fireworks.c: In function 'main':
fireworks.c:44:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   44 |  scanf("%d%d", &n, &m), n_ = n + m;
      |  ^~~~~~~~~~~~~~~~~~~~~
fireworks.c:46:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   46 |   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