Submission #599145

#	Time	Username	Problem	Language	Result	Execution time	Memory
599145		jophyyjh	Job Scheduling (IOI19_job)	C++14	24 / 100	127 ms	19124 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;

const ll INF = 0x3f3f3f3f3f3f;


struct node_t {
	int node;
	double weight;
};

inline bool operator>(const node_t& n1, const node_t& n2) {
	return n1.weight > n2.weight || (n1.weight == n2.weight && 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, std::vector<node_t>, std::greater<node_t>> pq;
	pq.emplace(node_t{0, -INF});
	while (!pq.empty()) {
		int t = pq.top().node;
		pq.pop();
		time += d[t], cost += time * u[t];
		for (int neighb : graph[t]) {
			double weight = INF;
			if (u[neighb] > 0)
				weight = double(d[neighb]) / u[neighb];
			pq.emplace(node_t{neighb, weight});
		}
	}
	return cost;
}

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