| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1357361 | yogesh_sane | Job Scheduling (IOI19_job) | C++20 | 0 ms | 0 KiB |
#include "job.h"
using namespace std;
using ll = long long;
struct DSU {
vector<int> link, sz, u, d;
vector<vector<int>> seq;
DSU(int n, vector<int> &U, vector<int> &D) {
sz.resize(n, 1);
link.resize(n);
iota(link.begin(), link.end(), 0);
seq.resize(n);
for (int i = 0; i < n; i++) seq[i].push_back(i);
u = U;
d = D;
}
int find(int x) {
while (x != link[x]) x = link[x];
return x;
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
sz[a] += b;
link[b] = a;
seq[a].push_back(b);
u[a] += u[b];
d[a] += d[b];
}
ll cur_time = 0, ans = 0;
void calc(int a, vector<int> &U, vector<int> &D) {
for (int i = 0; i < seq[a].size(); i++) {
if (seq[a][i] == a) {
cur_time += D[seq[a][i]];
ans += cur_time*U[seq[a][i]];
}
else calc(seq[a][i], U, D);
}
}
};
struct s {
int u, d;
int i;
bool operator<(const s &other) const {
// u/d < other.u/other.d
return 1ll*u*other.d < 1ll*d*other.u;
}
};
long long scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
int n = p.size();
vector<vector<int>> adj(n);
for (int i = 1; i < n; i++) adj[p[i]].push_back(i);
multiset<s> m;
for (int i = 1; i < n; i++) m.insert({u[i], d[i], i});
DSU dsu(n, u, d);
while (!m.empty()) {
s a = *m.rbegin();
m.erase(--m.end());
int x = dsu.find(p[a.i]);
if (x != 0){
auto it = m.find({dsu.u[x], dsu.d[x], x});
if(it != m.end())
m.erase(it);
}
dsu.merge(x, a.i);
if (x != 0) m.insert({dsu.u[x], dsu.d[x], x});
}
dsu.calc(0, u, d);
return dsu.ans;
}