#include "job.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pld pair<ld, ll>
#define fi first
#define se second
using namespace std;
const int N = 4e5+5;
const int M = 205;
const ll mod = 1e9+7;
const ld base = 1e-7;
ll n, m, k, ans, lab[N], cost[N], tim[N], id[N], par[N], t;
ld d[N];
struct node
{
bool operator ()(ll x, ll y) const
{
if(cost[x] * tim[y] == cost[y] * tim[x])return x < y;
cost[x] * tim[y] > cost[y] * tim[x];
}
};
ll findp(ll u)
{
return lab[u] < 0 ? u : lab[u] = findp(lab[u]);
}
priority_queue<pld> pq;
ll scheduling_cost(vector<int> p, vector<int> c, vector<int> di)
{
n = p.size();
fill_n(lab, n+1, -1);
for(int i = 1; i <= n; i ++)
{
par[i] = p[i-1]+1;
cost[i] = c[i-1];
tim[i] = di[i-1];
d[i] = 1.0 * cost[i] / tim[i];
pq.push({d[i], i});
//cout << cost[i] <<" "<<tim[i]<<" ";
}
while(!pq.empty())
{
pld u = pq.top();
pq.pop();
if(abs(d[u.se]-u.fi) > base)continue;
//cout << (ld)u.fi <<" ";
if(!par[u.se] || d[findp(par[u.se])] == -1)
{
t += tim[u.se];
ans += t * cost[u.se];
d[u.se] = -1;
}
else
{
ll v = findp(par[u.se]);
ans -= cost[v] * tim[u.se];
cost[v] += cost[u.se];
tim[v] += tim[u.se];
lab[u.se] = v;
d[v] = 1.0 * cost[v] / tim[v];
pq.push({d[v], v});
}
}
return ans;
}
void sol()
{
vector<int> p, d, u;
cin >> n;
p.resize(n);
d.resize(n);
u.resize(n);
for(int i = 0; i < n; i ++)cin >> p[i];
for(int i = 0; i < n; i ++)cin >> u[i];
for(int i = 0; i < n; i ++)cin >> d[i];
cout << scheduling_cost(p, u, d);
}
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
#define task "INSSORT"
if(fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int test = 1;
//cin >> test;
while(test -- > 0)sol();
return 0;
}
/*
3
-1 0 0
5 2 5
3 4 1
*/
Compilation message
job.cpp: In member function 'bool node::operator()(long long int, long long int) const':
job.cpp:22:20: warning: statement has no effect [-Wunused-value]
22 | cost[x] * tim[y] > cost[y] * tim[x];
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
job.cpp: In function 'int main()':
job.cpp:90:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
job.cpp:91:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccSRdiSr.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc1nFNIq.o:job.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
