#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;
}
| # |
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 |
| # |
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 |
- |
| # |
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 |
- |
| # |
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 |
- |
