Submission #135165

#	Time	Username	Problem	Language	Result	Execution time	Memory
135165		sebinkim	Fireworks (APIO16_fireworks)	C++14	100 / 100	371 ms	59740 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

priority_queue <ll> P[303030];
vector <ll> V[303030];
ll S[303030], C[303030];
ll n, m, ans;

void merge(ll p, ll q)
{
	if(P[p].size() < P[q].size()) swap(P[p], P[q]);
	for(; !P[q].empty(); P[q].pop()) P[p].push(P[q].top());
	S[p] += S[q];
}

void dfs(ll p)
{
	ll x, y, s = 0;
	
	S[p] = C[p];
	
	for(ll &t: V[p]){
		dfs(t); s ++;
		merge(p, t);
	}
	
	if(s == 0){
		P[p].push(C[p]); P[p].push(C[p]);
	}
	else{
		for(; s>1; s--) P[p].pop();
		x = P[p].top(); P[p].pop();
		y = P[p].top(); P[p].pop();
		P[p].push(x + C[p]); P[p].push(y + C[p]);
	}
}

int main()
{
	ll i, p, x;
	
	scanf("%lld%lld", &n, &m);
	
	for(i=2; i<=n+m; i++){
		scanf("%lld%lld", &p, C + i);
		V[p].push_back(i);
	}
	
	dfs(1);
	
	x = P[1].top(); P[1].pop();
	P[1].push(0);
	
	for(i=0; !P[1].empty(); i--){
		ans += i * (x - P[1].top());
		x = P[1].top(); P[1].pop();
	}
	
	printf("%lld\n", S[1] + ans);
	
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
fireworks.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &p, C + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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