Submission #1357051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1357051		toast12	Job Scheduling (IOI19_job)	C++20	12 / 100	58 ms	16060 KiB

job

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

using ll = long long;

long long scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
    int n = p.size();
    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) adj[p[i]].push_back(i);
    priority_queue<pair<int, int>> pq;
    ll cur_time = 0, ans = 0;
    pq.push({u[0], 0});
    while (!pq.empty()) {
        int i = pq.top().second;
        pq.pop();
        ans += u[i]*(cur_time+d[i]);
        cur_time += d[i];
        for (auto e : adj[i]) pq.push({u[e], e});
    }
	return ans;
}

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