Submission #705879

#	Time	Username	Problem	Language	Result	Execution time	Memory
705879		600Mihnea	Fireworks (APIO16_fireworks)	C++17	100 / 100	199 ms	46932 KiB

fireworks

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

typedef long long ll;

signed main()
{
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif

	int __, n;
	cin >> __ >> n;
	n += __;
	vector<vector<int>> g(n);
	vector<int> up(n, 0);
	vector<priority_queue<ll>> pqs(n);
	for (int i = 1; i < n; i++)
	{
		int par;
		cin >> par >> up[i];
		par--;
		assert(0 <= par && par < i);
		g[par].push_back(i);
	}
	ll sol = 0;
	for (int i = 0; i < n; i++)
	{
		sol += up[i];
	}
	for (int i = n - 1; i >= 0; i--)
	{
		if (g[i].empty())
		{
			pqs[i].push(up[i]);
			pqs[i].push(up[i]);
			continue;
		}
		for (auto& j : g[i])
		{
			if ((int)pqs[i].size() < (int)pqs[j].size())
			{
				swap(pqs[i], pqs[j]);
			}
			while (!pqs[j].empty())
			{
				pqs[i].push(pqs[j].top());
				pqs[j].pop();
			}
		}
		for (int s = 1; s <= (int)g[i].size() - 1; s++)
		{
			pqs[i].pop();
		}
		ll x = pqs[i].top() + up[i]; 
		pqs[i].pop();
		ll y = pqs[i].top() + up[i]; 
		pqs[i].pop();
		pqs[i].push(x);
		pqs[i].push(y);
	}
	pqs[0].pop();
	while (!pqs[0].empty())
	{
		sol -= pqs[0].top();
		pqs[0].pop();
	}
	cout << sol << "\n";
	return 0;
}

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