Submission #1060833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060833		boyliguanhan	Job Scheduling (IOI19_job)	C++17	100 / 100	291 ms	21700 KiB

job

#include "job.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu{
    int par[1<<18];
    int abp(int n){
        return par[n]?par[n]=abp(par[n]):n;
    }
    void merge(int a,int b){
        a=abp(a+2),b=abp(b+2);
        par[b]=a;
    }
    int comp(int n){
        return abp(n+2)-2;
    }
} DDT;
struct DATA{
    long long timetaken,value,i;
    DATA(long long u,long long d,int ind){
        value=u,timetaken=d,i=ind;
    }
    DATA(){
        timetaken=1e9;
        value=1;
        i=-1;
    }
    friend bool operator<(const DATA &a,const DATA&b){
        return make_pair(a.timetaken*b.value,a.i)<
                make_pair(b.timetaken*a.value,b.i);
    }
};
set<DATA>pq;
long long scheduling_cost(std::vector<int> p, std::vector<int> _u, std::vector<int> _d) {
    vector<long long>u,d;
    int N=p.size();
    long long curtime=0,ans=0;
    for(int i=0;i<N;i++)
        u.push_back(_u[i]),
        d.push_back(_d[i]),
        ans+=u[i]*d[i];
    for(int i=0;i<N;i++)
        pq.insert(DATA(u[i],d[i],i));
    while(pq.size()){
        int i=pq.begin()->i;
        pq.erase(DATA(u[i],d[i],i));
        if(DDT.comp(p[i])==-1){
            ans+=curtime*u[i];
            curtime+=d[i];
            DDT.merge(-1,i);
        } else {
            int mer=DDT.comp(p[i]);
            pq.erase(DATA(u[mer],d[mer],mer));
            DDT.merge(mer,i);
            ans+=d[mer]*u[i];
            u[mer]+=u[i];d[mer]+=d[i];
            pq.insert(DATA(u[mer],d[mer],mer));
        }
    }
    return ans;
}

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