Submission #81681

#	Time	Username	Problem	Language	Result	Execution time	Memory
81681		memikakizaki	Fireworks (APIO16_fireworks)	C++14	7 / 100	2 ms	696 KiB

fireworks

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author memikakizaki
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
using namespace std;
#define long long long

class Fireworks {
	int n, m;
	vector<vector<pair<int,int> > > g;

	vector<long> optL, optR, val;
	void dfs(int u, int wpar = 0) {
		val[u] = 0;
		if(g[u].empty()) {
			optL[u] = optR[u] = wpar;
			return;
		}

		priority_queue<long> pql;
		priority_queue<long, vector<long>, greater<long> > pqr;

		for(auto pr: g[u]) {
			int v, w;
			tie(v, w) = pr;
			dfs(v, w);
		}
		for(auto pr: g[u]) {
			int v, w;
			tie(v, w) = pr;
//			cout << "ord " << u << ' ' << v << ' ' << (pql.empty() ? -1 : pql.top()) << ' ' << (pqr.empty() ? -1 : pqr.top()) << endl;
			if(!pqr.empty() && optL[v] >= pqr.top()) val[u] += val[v] + optL[v] - pqr.top();//, cout << "val " << val[v] << ' ' << optL[v] << ' ' << pqr.top() << endl;
			else if(!pql.empty() && optR[v] <= pql.top()) val[u] += val[v] + pql.top() - optR[v];//, cout << "val " << val[v] << ' ' << optR[v] << ' ' << pql.top() << endl;
			else val[u] += val[v];

			if(!pql.empty() && optL[v] <= pql.top()) pql.push(optL[v]);
			else pqr.push(optL[v]);

			if(!pqr.empty() && optR[v] >= pqr.top()) pqr.push(optR[v]);
			else pql.push(optR[v]);

			assert((pql.size() + pqr.size()) % 2 == 0 && (pql.empty() || pqr.empty() || pql.top() <= pqr.top()));
			while(pql.size() > pqr.size()) pqr.push(pql.top()), pql.pop();
			while(pqr.size() > pql.size()) pql.push(pqr.top()), pqr.pop();
		}

		optL[u] = pql.top() + wpar;
		optR[u] = pqr.top() + wpar;
//		cout << u << ' ' << optL[u] << ' ' << optR[u] << ' ' << val[u] << endl << endl;
	}

public:
	void solve(istream& cin, ostream& cout) {
		cin >> n >> m;
		n += m;

		g = vector<vector<pair<int,int> > >(n);
		optL = vector<long>(n);
		optR = vector<long>(n);
		val = vector<long>(n);

		for(int i = 1, p, c; i < n; i++) {
			cin >> p >> c;
			g[p-1].emplace_back(i, c);
		}

		dfs(0);
		cout << val[0] << endl;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	Fireworks solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

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