Submission #442714

#	Time	Username	Problem	Language	Result	Execution time	Memory
442714		FlowerOfSorrow	Fireworks (APIO16_fireworks)	C++17	55 / 100	2096 ms	83660 KiB

fireworks

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

template<class F>
struct y_combinator_result{
	F f;
	template<class T> explicit y_combinator_result(T &&f): f(forward<T>(f)){ }
	template<class ...Args> decltype(auto) operator()(Args &&...args){ return f(ref(*this), forward<Args>(args)...); }
};
template<class F>
decltype(auto) y_combinator(F &&f){
	return y_combinator_result<decay_t<F>>(forward<F>(f));
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> adj(n + m);
	vector<int> par_w(n + m);
	for(auto u = 1; u < n + m; ++ u){
		int p;
		cin >> p >> par_w[u], -- p;
		adj[p].push_back(u);
	}
	auto res = y_combinator([&](auto self, int u)->pair<pair<int, long long>, priority_queue<long long>>{
		pair<int, long long> line{};
		priority_queue<long long> pq;
		if(u >= n){
			line = {1, -par_w[u]};
			pq = priority_queue<long long>{{}, vector<long long>(2, par_w[u])};
		}
		else{
			for(auto v: adj[u]){
				auto res_v = self(v);
				auto &[line_v, pq_v] = res_v;
				line.first += line_v.first, line.second += line_v.second;
				if((int)pq.size() < (int)pq_v.size()){
					swap(pq, pq_v);
				}
				while(!pq_v.empty()){
					pq.push(pq_v.top());
					pq_v.pop();
				}
			}
			while(line.first > 1){
				-- line.first;
				line.second += pq.top();
				pq.pop();
			}
			array<long long, 2> store{};
			for(auto rep = 0; rep < 2; ++ rep){
				store[rep] = pq.top() + par_w[u];
				pq.pop();
			}
			for(auto x: store){
				pq.push(x);
			}
			line.second -= par_w[u];
		}
		return {line, pq};
	})(0);
	cout << 1LL * res.first.first * res.second.top() + res.first.second << "\n";
	return 0;
}

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

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