Submission #599139

#	Time	Username	Problem	Language	Result	Execution time	Memory
599139		jophyyjh	Job Scheduling (IOI19_job)	C++14	12 / 100	117 ms	19248 KiB

job

/**
 * What an interesting pratice contest problem!
 * 
 * Time Complexity: O(n * log(n) + m)	(m is the num of edges)
 * Implementation 1
*/

#include <bits/stdc++.h>
#include "job.h"

typedef long long	ll;
typedef std::vector<int> 	vec;


struct node_t {
	int node, u;
};

inline bool operator<(const node_t& n1, const node_t& n2) {
	return n1.u < n2.u || (n1.u == n2.u && n1.node < n2.node);
}

ll scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
	int n = p.size();
	std::vector<vec> graph(n, vec());	// a reversed graph
	for (int i = 1; i < n; i++)
		graph[p[i]].emplace_back(i);

	ll time = 0, cost = 0;
	std::priority_queue<node_t> pq;
	pq.emplace(node_t{0, u[0]});
	while (!pq.empty()) {
		int t = pq.top().node;
		pq.pop();
		time += d[t], cost += time * u[t];
		for (int neighb : graph[t])
			pq.emplace(node_t{neighb, u[neighb]});
	}
	return cost;
}

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