Submission #40099

#	Time	Username	Problem	Language	Result	Execution time	Memory
40099		user202729	Fireworks (APIO16_fireworks)	C++14	100 / 100	797 ms	53580 KiB

fireworks

#ifndef _GLIBCXX_DEBUG
#define NDEBUG
#endif
#include <cassert>

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

#ifdef Sublime
#include <iostream>
#include <sstream>
#define cin cin__
namespace std{std::stringstream cin(R"(
4 6
1 5
2 5
2 8
3 3
3 2
3 3
2 9
4 4
4 3
)");}
#endif // Sublime


template <typename T>
std::multiset<T> merge(std::multiset<T> a, std::multiset<T> b) {
	if (a.size() < b.size()) std::swap(a, b);
	a.insert(b.begin(), b.end()); // move iterator?
	return a;
}

struct function {
	int zero_slope; // negative
	int64_t zero_value;
	std::multiset<int64_t> switches;
}; // convex piecewise-linear function 
// with derivative delta of (multiple of) 1

function operator+(function a, function b) {
	return {
		a.zero_slope + b.zero_slope,
		a.zero_value + b.zero_value,
		merge(std::move(a.switches), std::move(b.switches))
	};
}

struct node {
	size_t parent; int64_t parent_len;

	// consider the function **after** connected to parent.
	function fn;
};

std::istream& operator >> (std::istream& str, node & a) {
	str >> a.parent >> a.parent_len;
	--a.parent;
	return str;
}

int main() {
	size_t nbranch, nleaf;
	std::cin >> nbranch >> nleaf;

	std::vector<node> nodes (nbranch + nleaf);

	// read input
	for (size_t i = 1; i < nodes.size(); ++i) {
		std::cin >> nodes[i];
	}

	for (size_t i = nodes.size(); i --> 1; ) {
		node& n = nodes[i];
		if (i >= nbranch) { // process leaves
			n.fn.switches.insert({
				n.parent_len, 
				n.parent_len}); // twice
			n.fn.zero_slope = 1;
			n.fn.zero_value = n.parent_len;
		} else { // branches
			// so now n.fn is the sum of the (fn)'s
			// of the node's children.
			for (int i = n.fn.switches.size() - 
				(n.fn.zero_slope + 1); i --> 0;)
				n.fn.switches.erase(--n.fn.switches.end());
			n.fn.zero_value += n.parent_len;

			auto a = --n.fn.switches.end(); auto _a = *a; n.fn.switches.erase(a);
			auto b = --n.fn.switches.end(); auto _b = *b; n.fn.switches.erase(b);
			n.fn.switches.insert({_a + n.parent_len, _b + n.parent_len});

			assert((int) n.fn.switches.size() == n.fn.zero_slope + 1);

		}
		// add to its parent
		nodes[n.parent].fn = std::move(nodes[n.parent].fn) + std::move(n.fn);
	}

	function f = std::move(nodes[0].fn);

	assert((int) f.switches.size() >= f.zero_slope);

	for (int i = f.switches.size() - f.zero_slope; i --> 0;)
		f.switches.erase(--f.switches.end());

	assert((int) f.switches.size() == f.zero_slope);

	int last_slope = f.zero_slope;
	int64_t last_x = 0, last_y = f.zero_value;
	for (int64_t x : f.switches) {
		last_y -= last_slope * (x - last_x);
		last_x = x;
		--last_slope;
	}

	assert(last_slope == 0);
	std::cout << last_y << '\n';

	return 0;
}

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