Submission #367370

#	Time	Username	Problem	Language	Result	Execution time	Memory
367370		PurpleCrayon	Job Scheduling (IOI19_job)	C++17	0 / 100	1 ms	544 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);
    }
    cout << ans << '\n';
}

Compilation message (stderr)

job.cpp: In function 'll scheduling_cost(std::vector<int>, std::vector<int>, std::vector<int>)':
job.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
   28 | }
      | ^

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