#include "job.h"
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <utility>
#include <cstring>
#include <vector>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<pll, int> entry;
struct comp {
bool operator()(entry a, entry b) const {
int av = a.fi.fi * b.fi.se;
int bv = a.fi.se * b.fi.fi;
if (av != bv) {
return av < bv;
}
return a.se < b.se;
}
};
set<entry, comp> s;
vector<int> v[200005];
vector<int> ord;
int N, uf[200005];
ll uu[200005], dd[200005];
int f(int x) { if (uf[x] == x) return x; return uf[x] = f(uf[x]); }
void un(int x, int y) { uf[f(x)] = f(y); }
void dfs(int x) {
ord.push_back(x);
for (int i = 0; i < v[x].size(); i++) {
dfs(v[x][i]);
}
}
ll scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
int N = p.size();
for (int i = 0; i < N; i++) uf[i] = i;
for (int i = 1; i < N; i++) {
uu[i] = u[i];
dd[i] = d[i];
v[i].clear();
}
for (int i = 1; i < N; i++) s.insert({ { u[i], d[i] }, i });
while (s.size() > 0) {
auto it = --s.end();
entry e = *it;
s.erase(it);
assert(f(e.se) == e.se);
int par = p[e.se];
// Merge with parent
ll nu = uu[f(par)] + uu[e.se];
ll nd = dd[f(par)] + dd[e.se];
s.erase({ { uu[f(par)], dd[f(par)] }, f(par) });
v[f(par)].push_back(e.se);
un(e.se, par);
uu[f(par)] = nu;
dd[f(par)] = nd;
if (f(par) != 0) s.insert({ { uu[f(par)], dd[f(par)] }, f(par) });
}
dfs(0);
ll tm = 0, ans = 0;
for (int i = 0; i < ord.size(); i++) {
tm += d[ord[i]];
ans += tm * u[ord[i]];
}
return ans;
}
Compilation message
job.cpp: In function 'void dfs(int)':
job.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v[x].size(); i++) {
~~^~~~~~~~~~~~~
job.cpp: In function 'll scheduling_cost(std::vector<int>, std::vector<int>, std::vector<int>)':
job.cpp:56:3: error: 'assert' was not declared in this scope
assert(f(e.se) == e.se);
^~~~~~
job.cpp:56:3: note: suggested alternative: 'qsort'
assert(f(e.se) == e.se);
^~~~~~
qsort
job.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ord.size(); i++) {
~~^~~~~~~~~~~~
