Submission #145187

#	Time	Username	Problem	Language	Result	Execution time	Memory
145187		ecnerwala	Job Scheduling (IOI19_job)	C++14	100 / 100	324 ms	18036 KiB

job

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

using ll = long long;

ll scheduling_cost(vector<int> P, vector<int> U_, vector<int> D_) {
	vector<ll> U(U_.begin(), U_.end());
	vector<ll> D(D_.begin(), D_.end());
	int N = int(P.size());
	ll ans = 0;
	for (int i = 0; i < N; i++) {
		ans += U[i] * D[i];
	}

	// build things earlier with high U[i] / D[i]
	auto cmp = [](pair<pair<ll, ll>, int> i, pair<pair<ll, ll>, int> j) {
		// returns true if j comes first
		return j.first.second * i.first.first < i.first.second * j.first.first;
	};

	priority_queue<pair<pair<ll, ll>, int>, vector<pair<pair<ll, ll>, int>>, decltype(cmp)> pq(cmp);
	vector<char> dead(N);

	for (int i = 1; i < N; i++) {
		if (U[i] == 0 && D[i] == 0) {
			dead[i] = true;
		} else {
			pq.emplace(pair<ll, ll>(U[i], D[i]), i);
		}
	}

	int cnt = 0;
	while (!pq.empty()) {
		auto it = pq.top(); pq.pop();
		int cur = it.second;
		if (dead[cur] || it.first != pair<ll, ll>(U[cur], D[cur])) continue;

		int prv = P[cur];
		while (dead[prv]) {
			assert(0 <= P[prv] && P[prv] < prv);
			prv = P[prv];
		}

		for (int v = P[cur]; v != prv; ) {
			int nxt = P[v];
			P[v] = prv;
			v = nxt;
		}

		ans += D[prv] * U[cur];
		U[prv] += U[cur];
		D[prv] += D[cur];
		dead[cur] = true;
		if (prv != 0) {
			pq.emplace(pair<ll, ll>(U[prv], D[prv]), prv);
		}
		cnt++;
	}
	return ans;
}

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