oj.uz

Submission #475076

# Submission time Handle Problem Language Result Execution time Memory
475076 2021-09-21T04:15:11 Z cpp219 Job Scheduling (IOI19_job) C++14
0 / 100
 1 ms 1868 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1868 KB Output isn't correct
2 Halted 0 ms 0 KB -