Submission #1234506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234506		PlayVoltz	Fireworks (APIO16_fireworks)	C++20	100 / 100	213 ms	73096 KiB

fireworks

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
using namespace std;
 
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

vector<int> m, c;
vector<priority_queue<int> > pq;
vector<vector<pii> > graph;

void dfs(int node, int p){
	if (graph[node].empty()){
		m[node]=1;
		c[node]=-p;
		pq[node].push(p);
		pq[node].push(p);
		return;
	}
	for (auto num:graph[node]){
		dfs(num.fi, num.se);
		m[node]+=m[num.fi];
		c[node]+=c[num.fi];
		if (pq[node].size()<pq[num.fi].size())swap(pq[node], pq[num.fi]);
		while (pq[num.fi].size()){
			pq[node].push(pq[num.fi].top());
			pq[num.fi].pop();
		}
	}
	while (m[node]>1){
		--m[node];
		c[node]+=pq[node].top();
		pq[node].pop();
	}
	int a=pq[node].top();
	pq[node].pop();
	int b=pq[node].top();
	pq[node].pop();
	pq[node].push(a+p);
	pq[node].push(b+p);
	c[node]-=p;
}

int32_t main(){
	int n, k, a, b;
	cin>>n>>k;
	graph.resize(n+k+1);
	m.resize(n+k+1, 0);
	c.resize(n+k+1, 0);
	pq.resize(n+k+1);
	for (int i=2; i<=n+k; ++i)cin>>a>>b, graph[a].pb(mp(i, b));
	dfs(1, 0);
	while (m[1]>0){
		--m[1];
		c[1]+=pq[1].top();
		pq[1].pop();
	}
	cout<<c[1];
}

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