제출 #40089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40089		user202729	Fireworks (APIO16_fireworks)	C++14	7 / 100	0 ms	2020 KiB

fireworks

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

#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


struct node {
	size_t parent; int parent_len;

	// consider the function after connected to parent.
	long long x0, x1;
	long long value;
};

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);
	std::vector<std::vector<size_t>> adjlist (nbranch);
	for (size_t i = 1; i < nodes.size(); ++i) {
		std::cin >> nodes[i];
		adjlist[nodes[i].parent].push_back(i);
	}
	for (size_t i = nodes.size(); i --> nbranch; ) {
		nodes[i].x0 = nodes[i].x1 = nodes[i].parent_len;
		// adjlist[i].value = 0; // already default
	}
	for (size_t i = nbranch; i --> 0; ) {
		std::vector<int> increments;
		for (size_t c : adjlist[i]) {
			increments.push_back(nodes[c].x0);
			increments.push_back(nodes[c].x1);
		}
		std::sort(increments.begin(), increments.end());
		// nth_element would work too
		nodes[i].x0 = increments[adjlist[i].size()-1];
		nodes[i].x1 = increments[adjlist[i].size()];

		long long val = 0;
		int x = nodes[i].x0;
		for (size_t c : adjlist[i]) {
			 val += nodes[c].value;
			 if (x < nodes[c].x0)
			 	val += nodes[c].x0 - x;
			 if (x > nodes[c].x1)
			 	val += x - nodes[c].x1;
		}
		nodes[i].value = val;

		// increment by parent_len now
		nodes[i].x0 += nodes[i].parent_len;
		nodes[i].x1 += nodes[i].parent_len;
	}

	std::cout << nodes[0].value << '\n';

	return 0;
}

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