oj.uz

Submission #40090

# Submission time Handle Problem Language Result Execution time Memory
40090 2018-01-26T16:01:07 Z user202729 Fireworks (APIO16_fireworks) C++14
7 / 100
 0 ms 2020 KB 
#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.
	int64_t x0, x1;
	int64_t 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<int64_t> 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()];

		int64_t val = 0;
		int64_t 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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 0 ms 2020 KB Output is correct
3 Correct 0 ms 2020 KB Output is correct
4 Correct 0 ms 2020 KB Output is correct
5 Correct 0 ms 2020 KB Output is correct
6 Correct 0 ms 2020 KB Output is correct
7 Correct 0 ms 2020 KB Output is correct
8 Correct 0 ms 2020 KB Output is correct
9 Correct 0 ms 2020 KB Output is correct
10 Correct 0 ms 2020 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 0 ms 2020 KB Output is correct
3 Incorrect 0 ms 2020 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 0 ms 2020 KB Output is correct
3 Correct 0 ms 2020 KB Output is correct
4 Correct 0 ms 2020 KB Output is correct
5 Correct 0 ms 2020 KB Output is correct
6 Correct 0 ms 2020 KB Output is correct
7 Correct 0 ms 2020 KB Output is correct
8 Correct 0 ms 2020 KB Output is correct
9 Correct 0 ms 2020 KB Output is correct
10 Correct 0 ms 2020 KB Output is correct
11 Correct 0 ms 2020 KB Output is correct
12 Correct 0 ms 2020 KB Output is correct
13 Incorrect 0 ms 2020 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 0 ms 2020 KB Output is correct
3 Correct 0 ms 2020 KB Output is correct
4 Correct 0 ms 2020 KB Output is correct
5 Correct 0 ms 2020 KB Output is correct
6 Correct 0 ms 2020 KB Output is correct
7 Correct 0 ms 2020 KB Output is correct
8 Correct 0 ms 2020 KB Output is correct
9 Correct 0 ms 2020 KB Output is correct
10 Correct 0 ms 2020 KB Output is correct
11 Correct 0 ms 2020 KB Output is correct
12 Correct 0 ms 2020 KB Output is correct
13 Incorrect 0 ms 2020 KB Output isn't correct
14 Halted 0 ms 0 KB -