| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1040548 | Requiem | Job Scheduling (IOI19_job) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "job.h"
#define ll long long
#define ii pair<int, int>
#define iii pair<int,ii>
#define vii vector<ii>
#define fi first
#define se second
#define endl '\n'
#define show(T) {for (auto x:T) cout<<x<<' ';cout<<endl;}
#define all(T) T.begin(),T.end()
using namespace std;
const double eps = 0.0000001;
const int mod = 1e9+7;
const int N = 200005;
const int MATRIX_SIZE = 64;
const int BLOCK=500;
ll n,w[N],t[N],p[N],ans,par[N],sz[N],tmp_w[N],tmp_t[N],trol;
vector <ll> G[N];
// bool ok(int pos1,int pos2){return w[pos1]*t[pos2]>w[pos2]*t[pos1];}
struct job{
ll v,w,t;
};
struct cmp{
bool operator () (job a,job b){if (a.w*b.t==b.w*a.t) return a.v<b.v;return a.w*b.t>b.w*a.t;}
};
set <job,cmp> luu[N];
list <ll> T[N];
ll get(ll x){
if (x!=par[x]) return par[x]=get(par[x]);
return x;
}
void noi(ll a,ll b){
a=get(a);
b=get(b);
if (a==b) return;
ll nguoi_giu_chia_khoa;
if (T[a].size()>T[b].size()){
nguoi_giu_chia_khoa=a;
while (!T[b].empty()){
T[a].push_back(T[b].front());
T[b].pop_front();
}
}
else{
nguoi_giu_chia_khoa=b;
while (!T[a].empty()){
T[b].push_front(T[a].back());
T[a].pop_back();
}
}
if (sz[a]<sz[b]) swap(a,b);
if (nguoi_giu_chia_khoa!=a)
swap(T[b],T[a]);
sz[a]+=sz[b];
par[b]=a;
w[a]+=w[b];
t[a]+=t[b];
}
void DFS(ll v){
// trol=v;
for (auto child:G[v]){
DFS(child);
// trol=v;
if (luu[child].size()>luu[v].size()) swap(luu[v],luu[child]);
for (auto x:luu[child]) luu[v].insert(x);
}
job tam=*luu[v].begin();
while (tam.w*t[get(v)]>w[get(v)]*tam.t){
luu[v].erase(luu[v].begin());
noi(v,tam.v);
if (luu[v].empty()) break;
tam=*luu[v].begin();
}
luu[v].insert({get(v),w[get(v)],t[get(v)]});
}
ll scheduling_cost(vector<int> _p, vector<int> _w, vector<int> _t) {
n=_p.size();
for (int i=1;i<=n;++i){
p[i]=_p[i-1];
G[p[i]].push_back(i);
par[i]=i;
sz[i]=1;
T[i].push_back(i);
}
for (int i=1;i<=n;++i){
w[i]=_w[i-1];
tmp_w[i]=w[i];
}
for (int i=1;i<=n;++i){
t[i]=_t[i-1];
tmp_t[i]=t[i];
}
DFS(1);
int d=0;
for (auto sus:luu[1]){
for (auto x:T[sus.v]){
d+=tmp_t[x];
ans+=tmp_w[x]*d;
}
}
return ans;
}