/**
* What an interesting pratice contest problem!
*
* Time Complexity: O(n * log(n) + m) (m is the num of edges)
* Implementation 1
*/
#include <bits/stdc++.h>
#include "job.h"
typedef long long ll;
typedef std::vector<int> vec;
struct node_t {
int node, u;
};
inline bool operator<(const node_t& n1, const node_t& n2) {
return n1.u < n2.u || (n1.u == n2.u && n1.node < n2.node);
}
ll scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
int n = p.size();
std::vector<vec> graph(n, vec()); // a reversed graph
for (int i = 1; i < n; i++)
graph[p[i]].emplace_back(i);
ll time = 0, cost = 0;
std::priority_queue<node_t> pq;
pq.emplace(node_t{0, u[0]});
while (!pq.empty()) {
int t = pq.top().node;
pq.pop();
time += d[t], cost += time * u[t];
for (int neighb : graph[t])
pq.emplace(node_t{neighb, u[neighb]});
}
return cost;
}
