Submission #367371

#	Time	Username	Problem	Language	Result	Execution time	Memory
367371		PurpleCrayon	Job Scheduling (IOI19_job)	C++17	24 / 100	196 ms	19180 KiB

job

#include "job.h"
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;

ll scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
    int n=sz(p);
    vector<vector<int>> ch(n);
    for (int i = 1; i < n; i++) ch[p[i]].push_back(i);

    auto cmp = [&](int i, int j) -> bool {
        return ll(d[j])*ll(u[i]) < ll(d[i])*ll(u[j]);
    };
    priority_queue<int, vector<int>, decltype(cmp)> roots(cmp);

    ll ans=0, t=0;
    roots.push(0);

    while (sz(roots)){
        int c=roots.top(); roots.pop();
        t += d[c], ans += t*u[c];
        for (auto nxt : ch[c]) roots.push(nxt);
    }
    return ans;
}

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