Submission #432219

#	Time	Username	Problem	Language	Result	Execution time	Memory
432219		Berted	Job Scheduling (IOI19_job)	C++14	24 / 100	195 ms	19768 KiB

job

#include "job.h"
#include <vector>
#include <cassert>
#include <algorithm>
#include <queue>
#define vi vector<int>
#define ll long long
#define pii pair<ll, ll>
#define ppi pair<pii, ll>
#define fst first
#define snd second

using namespace std;

int N;
pii A[200001];
vi adj[200001];

inline bool comp(const ppi &l, const ppi &r)
{
	return make_pair(l.fst.fst * r.fst.snd, l.snd) < make_pair(r.fst.fst * l.fst.snd, r.snd);
}

priority_queue<ppi, vector<ppi>, decltype(&comp)> pq(comp);

long long scheduling_cost(vi p, vi u, vi d) 
{
	N = p.size();
	ll t = 0, res = 0;
	for (int i = 1; i < N; i++) adj[p[i]].push_back(i);
	
	pq.push({{u[0], d[0]}, 0});
	while (pq.size())
	{
		int uu = pq.top().snd; pii vv = pq.top().fst; pq.pop();
		t += vv.snd; res += t * vv.fst;
		for (const auto &w : adj[uu])
		{
			pq.push({{u[w], d[w]}, w});
		}
	}
	return res;
}

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