Submission #24138

#	Time	Username	Problem	Language	Result	Execution time	Memory
24138		khsoo01	Fireworks (APIO16_fireworks)	C++11	100 / 100	673 ms	53576 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, p[300005], l[300005];

struct hull {
	ll p, i;
	multiset<ll> s;
} h[300005];

ll Pop (hull &A) {
	auto T = A.s.end(); T--;
	ll ret = *T;
	A.s.erase(T);
	return ret;
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=2;i<=n;i++) {
		scanf("%lld%lld",&p[i],&l[i]);
	}
	for(int i=1;i<=m;i++) {
		ll P, L;
		scanf("%lld%lld",&P,&L);
		h[P].i--;
		h[P].p += L;
		h[P].s.insert(L);
		h[P].s.insert(L);
	}
	for(int i=n;i>=2;i--) {
		while(h[i].s.size() > 1-h[i].i) Pop(h[i]);
		h[i].p += l[i];
		ll A = Pop(h[i]), B = Pop(h[i]);
		h[i].s.insert(A + l[i]);
		h[i].s.insert(B + l[i]);
		if(p[i] != 1 && h[p[i]].s.size() < h[i].s.size()) swap(h[p[i]], h[i]);
		while(!h[i].s.empty()) h[p[i]].s.insert(Pop(h[i]));
		h[p[i]].p += h[i].p;
		h[p[i]].i += h[i].i;
	}
	ll ans = h[1].p, cur = 0, grd = h[1].i;
	while(grd < 0) {
		ll nxt = (*h[1].s.begin());
		h[1].s.erase(h[1].s.begin());
		ans += grd * (nxt - cur);
		cur = nxt; grd++;
	}
	printf("%lld\n",ans);
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:33:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(h[i].s.size() > 1-h[i].i) Pop(h[i]);
                       ^
fireworks.cpp:20:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&m);
                         ^
fireworks.cpp:22:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&p[i],&l[i]);
                                ^
fireworks.cpp:26:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&P,&L);
                          ^

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