#include "job.h"
#include <bits/stdc++.h>
long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
int n=p.size();
struct _job
{
long long cost;
long long time;
int ind;
};
std::vector<int> par(n);
std::vector<_job> val(n);
long long ans=0;
for(int i=0;i<n;i++){
par[i]=i;
val[i].cost=(long long)u[i];
val[i].time=(long long)d[i];
val[i].ind=i;
ans+=val[i].cost*val[i].time;
}
auto concat_job=[&](_job &l,_job r)->void{
ans+=l.time*r.cost;
l.time+=r.time;
l.cost+=r.cost;
};
auto comp_job=[&](_job l,_job r)->bool{
return l.cost*r.time<l.time*r.cost;
};
auto root=[&](auto self,int a)->int{
if(a==par[a]) return a;
par[a]=self(self,par[a]);
return par[a];
};
std::priority_queue<_job,std::vector<_job>,std::function<bool(_job,_job)>> pq(comp_job);
int t=-1;
for(int i=0;i<n;i++){
if(p[i]==-1) t=i;
}
std::vector<int> seen(n);
for(int i=0;i<n;i++){
if(i!=t){
pq.push(val[i]);
}
}
while(!pq.empty()){
_job tmp=pq.top();
pq.pop();
if(seen[tmp.ind]) continue;
if(val[tmp.ind].cost!=tmp.cost||val[tmp.ind].time!=tmp.time) continue;
seen[tmp.ind]=1;
par[tmp.ind]=p[tmp.ind];
int r=root(root,tmp.ind);
concat_job(val[r],tmp);
if(r!=t) pq.push(val[r]);
}
return ans;
}
