Submission #331293

#	Time	Username	Problem	Language	Result	Execution time	Memory
331293		ttnhuy313	Job Scheduling (IOI19_job)	C++14	100 / 100	252 ms	20968 KiB

job

#include <bits/stdc++.h>

using namespace std;
#define int long long
typedef pair <int, int> ii;

const int N = 2e5 + 5;
int n, dp[N], cost[N], d[N], lab[N], res;

struct obj {
	int sum_d, sum_cost;
	bool operator < (const obj other) const {
		return sum_d * other.sum_cost > other.sum_d * sum_cost;
	}
	bool operator != (const obj other) const {
		return ii(sum_d, sum_cost) != ii(other.sum_d, other.sum_cost);
	}
} a[N];

int root(int x) {
	if (lab[x] == -1) return x;
	else return lab[x] = root(lab[x]);
}

int scheduling_cost(vector <int32_t> p, vector <int32_t> c, vector <int32_t> time) {
	memset(lab, -1, sizeof lab);	
	n = p.size();
	priority_queue <pair <obj, int>> pq;
	while (!pq.empty()) pq.pop();
	for (int i = 0; i < n; ++i) {
		cost[i] = c[i];
		d[i] = time[i];
		a[i] = {d[i], cost[i]};
		res += d[i] * cost[i];
		pq.push({a[i], i});
	}
	while (!pq.empty()) {
		obj cur = pq.top().first; int u = pq.top().second;
		pq.pop();
		if (cur != a[u] || u == 0) continue;
		int v = root(p[u]);
		res += a[v].sum_d * a[u].sum_cost;
		a[v].sum_d += a[u].sum_d; a[v].sum_cost += a[u].sum_cost;
		lab[u] = v;
		pq.push({a[v], v});
	}
	return res;
}

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