Submission #1025819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025819		jhinezeal123	Job Scheduling (IOI19_job)	C++14	0 / 100	6 ms	29276 KiB

job

#include <bits/stdc++.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;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 37