/**
* 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;
const ll INF = 0x3f3f3f3f3f3f;
struct node_t {
int node;
double weight;
};
inline bool operator>(const node_t& n1, const node_t& n2) {
return n1.weight > n2.weight || (n1.weight == n2.weight && 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, std::vector<node_t>, std::greater<node_t>> pq;
pq.emplace(node_t{0, -INF});
while (!pq.empty()) {
int t = pq.top().node;
pq.pop();
time += d[t], cost += time * u[t];
for (int neighb : graph[t]) {
double weight = INF;
if (u[neighb] > 0)
weight = double(d[neighb]) / u[neighb];
pq.emplace(node_t{neighb, weight});
}
}
return cost;
}
