// #include "job.h"
#include <bits/stdc++.h>
#ifdef OP_DEBUG
#include <algo/debug.h>
#else
#define debug(...) 26
#endif
using namespace std;
// #define int long long
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define TcT template <class T
const int MOD = (int)1e9 + 7, INF = (int)4e18 + 18;
TcT> bool minimize(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }
TcT> bool maximize(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }
void solve();
int32_t main() {
cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false);
int testcases = 1;
#define TC 0
if (TC) { cin >> testcases; } for (; testcases--;) { solve(); }
}
/* [Pham Hung Anh - 12I - Tran Hung Dao High School for Gifted Student] */
long long scheduling_cost(vector <int> p, vector <int> u, vector <int> d) {
vector <vector <int>> adj(sz(p));
for (int i = 1; i < sz(p); ++i)
adj[p[i]].emplace_back(i);
auto Merge = [&](vector<int> l, vector<int> r) {
int n = sz(l), m = sz(r);
vector <long long> pfa(n + 1), pfb(m + 1);
for (int i = 0; i < n; i++)
pfa[i + 1] = pfa[i] + d[l[i]];
for (int i = 0; i < m; i++)
pfb[i + 1] = pfb[i] + d[r[i]];
vector <vector <long long>> dp(n + 1, vector <long long> (m + 1, INF)); dp[0][0] = 0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i < n)
minimize(dp[i + 1][j], dp[i][j] + (pfa[i + 1] + pfb[j]) * u[l[i]]);
if (j < m)
minimize(dp[i][j + 1], dp[i][j] + (pfa[i] + pfb[j + 1]) * u[r[j]]);
}
}
vector <int> merged;
while (n > 0 || m > 0) {
if (n > 0 && dp[n][m] == dp[n - 1][m] + (pfa[n] + pfb[m]) * u[l[n - 1]]) {
merged.emplace_back(l[n - 1]);
n--;
} else if (m > 0 && dp[n][m] == dp[n][m - 1] + (pfa[n] + pfb[m]) * u[r[m - 1]]) {
merged.emplace_back(r[m - 1]);
m--;
}
}
reverse(all(merged));
return merged;
};
vector <vector <int>> job(sz(p));
auto dfs = [&](auto &&self, int u) -> void {
for (int v : adj[u]) {
self(self, v);
job[u] = Merge(job[u], job[v]);
}
job[u].insert(job[u].begin(), u);
};
dfs(dfs, 0);
long long tot_time = 0, ans = 0;
for (int id : job[0]) {
tot_time += d[id];
ans += tot_time * u[id];
}
return ans;
}
void solve() {
cout << scheduling_cost({ -1, 0, 0 }, { 5, 2, 5 }, { 3, 4, 1 }) << '\n';
}
// void solve() {
// int n; cin >> n;
// vector <int> P(n), W(n), T(n);
// for (int &p : P)
// cin >> p;
// for (int &w : W)
// cin >> w;
// for (int &t : T)
// cin >> t;
// vector <vector <int>> adj(n);
// for (int i = 1; i < n; ++i)
// adj[P[i]].emplace_back(i);
// int tot_time = 0, ans = 0;
// priority_queue <Info> pq; pq.push({ 0, W[0], T[0] });
// while (sz(pq)) {
// Info job = pq.top(); pq.pop();
// tot_time += T[job.id];
// ans += tot_time * W[job.id];
// for (int v : adj[job.id])
// pq.push({ v, W[v], T[v] });
// }
// cout << ans << '\n';
// }
Compilation message
/usr/bin/ld: /tmp/cciEEsHb.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccyhaY0a.o:job.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
