Submission #1127480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127480		MikolajKolek	Fireworks (APIO16_fireworks)	C++20	100 / 100	168 ms	89548 KiB

fireworks

//https://oj.uz/problem/view/APIO16_fireworks
//Solution by Mikołaj Kołek

#include "bits/stdc++.h"
#define intin *istream_iterator<int>(cin)

using namespace std;

struct Node {
	long long parentConnectionLength = 0, largestChild = -1;
	bool isExplosive = false;
	vector<int> children;	
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n = intin, m = intin;
	vector<Node> G(n + m);
	for(int i = 1; i < (n + m); i++) {
		G[intin - 1].children.push_back(i);
		G[i].parentConnectionLength = intin;
		G[i].isExplosive = (i >= n);
	}
	
	function<int(int)> DFS1 = [&] (int v) {
		int maxChildSize = -1, mySize = 1;
		
		for(int i = 0; i < G[v].children.size(); i++) {
			int childSize = DFS1(G[v].children[i]);
			mySize += childSize;
			
			if(childSize > maxChildSize) {
				maxChildSize = childSize;
				G[v].largestChild = i;
			}
		}
		
		return mySize;
	};
	DFS1(0);
	
	function <long long(int, priority_queue<long long>&)> DFS2 = [&] (int v, priority_queue<long long> &Q) {
		if(G[v].isExplosive) {
			Q.push(G[v].parentConnectionLength);
			Q.push(G[v].parentConnectionLength);
			
			return -G[v].parentConnectionLength;
		}
		
		long long b = DFS2(G[v].children[G[v].largestChild], Q);
		for(int i = 0; i < G[v].children.size(); i++) {
			if(i == G[v].largestChild)
				continue;
			
			priority_queue<long long> Q2;
			b += DFS2(G[v].children[i], Q2);
			
			while(!Q2.empty()) {
				Q.push(Q2.top());
				Q2.pop();
			}
		}
		
		for(int i = 0; i < (G[v].children.size() - ((v != 0) ? 1 : 0)); i++) {
			b += Q.top();
			Q.pop();
		}
		
		if(!Q.empty()) {
			long long top = Q.top(); Q.pop();
			
			if(!Q.empty()) {
				long long top2 = Q.top(); Q.pop();
				Q.push(top2 + G[v].parentConnectionLength);
			}
			
			Q.push(top + G[v].parentConnectionLength);
		}
		
		return b - G[v].parentConnectionLength;
	};
	
	priority_queue<long long> Q;
	cout << DFS2(0, Q);
	
	return 0;
}

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