Submission #475078

#	Time	Username	Problem	Language	Result	Execution time	Memory
475078		cpp219	Job Scheduling (IOI19_job)	C++14	0 / 100	149 ms	262148 KiB

job

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
typedef pair<ld,ll> LD;
const ll N = 2e5 + 9;
const ll inf = 1e9;
const ll esp = 1e-9;

ld d[N];
ll n,lab[N],ans,par[N],cost[N],Time[N],now;
priority_queue<LD> pq;

ll Find(ll u){
    if (lab[u] < 0) return u;
    return lab[u] = Find(lab[u]);
}

ll scheduling_cost(vector<int> p,vector<int> c,vector<int> D){
    memset(lab,-1,sizeof(lab)); n = p.size();
    for (ll i = 1;i <= n;i++){
        par[i] = p[i - 1] + 1; cost[i] = c[i - 1]; d[i] = D[i - 1];
        d[i] = 1.0*inf*cost[i]/d[i];
        pq.push({d[i],-i});
    }
    while(!pq.empty()){
        LD u = pq.top(); pq.pop(); u.sc *= -1;
        if (abs(d[u.sc] - u.fs) > esp) continue;
        if (!par[u.sc] || d[Find(u.sc)] == -1){
            now += Time[u.sc]; ans += now * cost[u.sc];
            d[u.sc] = -1;
        }
        else{
            ll v = Find(u.sc); ans -= cost[v] * Time[u.sc];
            cost[v] += cost[u.sc]; Time[v] += Time[u.sc];
            d[v] = 1.0*inf * cost[v]/Time[v]; lab[u.sc] = v;
            pq.push({d[v],-v});
        }
    }
    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