Submission #153951

#	Time	Username	Problem	Language	Result	Execution time	Memory
153951		songc	Fireworks (APIO16_fireworks)	C++14	100 / 100	367 ms	75876 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M;
LL C[303030], S[303030], Y[303030];
vector<int> adj[303030];
priority_queue<LL> PQ[303030];

void dfs(int u){
	if (adj[u].empty()){
		S[u] = -1, Y[u] = C[u];
		PQ[u].push(C[u]);
		PQ[u].push(C[u]);
		return;
	}

	for (int v : adj[u]){
		dfs(v);
		S[u] += S[v], Y[u] += Y[v];
		if (PQ[u].size() < PQ[v].size()) swap(PQ[u], PQ[v]);
		while (!PQ[v].empty()){
			PQ[u].push(PQ[v].top());
			PQ[v].pop();
		}
	}

	LL a=-1, b=-1;
	Y[u] += C[u];
	while (S[u] + PQ[u].size() > 1) PQ[u].pop();
	if (S[u] + PQ[u].size() == 1) a=PQ[u].top(), PQ[u].pop();
	if (S[u] + PQ[u].size() == 0) b=PQ[u].top(), PQ[u].pop();
	if (a != -1) PQ[u].push(a+C[u]);
	if (b != -1) PQ[u].push(b+C[u]);
}

int main(){
	scanf("%d %d", &N, &M);
	for (int i=2; i<=N+M; i++){
		int p;
		scanf("%d %lld", &p, &C[i]);
		adj[p].push_back(i);
	}
	dfs(1);
	LL x = PQ[1].top();
	PQ[1].pop();
	PQ[1].push(0);
	for (int i=0; !PQ[1].empty(); i++){
		Y[1] -= i * (x - PQ[1].top());
		x = PQ[1].top();
		PQ[1].pop();
	}
	printf("%lld\n", Y[1]);
	return 0;
}

Compilation message (stderr)

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

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