Submission #245887

#	Time	Username	Problem	Language	Result	Execution time	Memory
245887		Berted	Fireworks (APIO16_fireworks)	C++14	100 / 100	329 ms	84424 KiB

fireworks

#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <queue>
#define pub push_back
#define ll long long
#define vi vector<ll>
#define pii pair<int, int>
#define fst first
#define snd second
#define vpi vector<pii>

using namespace std;

const ll MX = 1e15;

int n, m;
vector<vpi> adj;
ll dp[301][301] = {}, res = MX, prec[301] = {};

struct slopeDS
{
	priority_queue<ll> pqL;
	priority_queue<ll, vi, greater<ll>> pqR;
	ll sft = 0, opt = 0;

	slopeDS(int x)
	{
		pqL.push(0); pqL.push(x);
		pqR.push(x); pqR.push(MX);
	}

	ll getL() {return pqL.top();}
	ll getR() {return pqR.top() + sft;}
	void pushL(ll val) {pqL.push(val);}
	void pushR(ll val) {pqR.push(val - sft);}
	void popL() {pqL.pop();}
	void popR() {pqR.pop();}
	int getSZ() {return pqL.size() + pqR.size();}

	void debugOutput(int id)
	{
		priority_queue<ll> cpqL = pqL;
		priority_queue<ll, vi, greater<ll>> cpqR = pqR;
		cout << "-------------------------------------------------------------------------\n";
		cout << "Slope DS ID : " << id << "\n";
		cout << "Left Slopes : ";
		while (cpqL.size()) {cout << cpqL.top() << " "; cpqL.pop();}
		cout << "\n";
		cout << "Right Slopes : ";
		while (cpqR.size()) {cout << cpqR.top() + sft << " "; cpqR.pop();}
		cout << "\n";
		cout << "OPT VAL : " << opt << "\n";
		cout << "-------------------------------------------------------------------------\n";
	}
};

inline void merge(slopeDS *&L, slopeDS *&R)
{
	if (L == nullptr) {L = R;}
	else if (R == nullptr) {R = L;}
	else
	{
		if (L -> getSZ() < R -> getSZ()) swap(L, R);
		L -> opt += R -> opt;
		while (R -> pqL.size())
		{
			ll pos = R -> getL(); R -> popL();
			if (pos <= L -> getR()) {L -> pushL(pos);}
			else
			{
				L -> opt += pos - L -> getR();
				L -> pushL(L -> getR()); L -> popR();
				L -> pushR(pos);
			}
		}
		while (R -> pqR.size())
		{
			ll pos = R -> getR(); R -> popR();
			if (pos >= L -> getL()) {L -> pushR(pos);}
			else
			{
				L -> opt += L -> getL() - pos;
				L -> pushR(L -> getL()); L -> popL();
				L -> pushL(pos);
			}
		}
	}
}

slopeDS* dfs(int u, int p, int val)
{
	if (adj[u].size() == 0) {return new slopeDS(val);}
	else
	{
		slopeDS* cur = nullptr;
		for (auto v : adj[u])
		{
			if (v.fst != p)
			{
				slopeDS* tmp = dfs(v.fst, u, v.snd);
				merge(cur, tmp);
			}
		}
		if (p != -1)
		{
			ll prev; prev = cur -> getL();
			cur -> sft += val;
			cur -> popL();
			cur -> pushL(prev + val);
			prev = cur -> getR();
			while (cur -> pqR.size()) cur -> popR();
			cur -> pushR(prev);
		}
		return cur;
	}
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n + m; i++) {adj.pub(vpi());}
	for (int i = 1; i < n + m; i++)
	{
		int p, v; cin >> p >> v;
		adj[p - 1].push_back({i, v});
	}
	slopeDS* ret = dfs(0, -1, 0);
	cout << ret -> opt << "\n";
	return 0;
}

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