Submission #1194338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194338		chaeryeong	Job Scheduling (IOI19_job)	C++20	100 / 100	523 ms	179600 KiB

job

#include "job.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 25;
vector <int> adj[MAXN];
ll u[MAXN], d[MAXN];
int n;
struct DSU {
	int par[MAXN];
	void init () {
		for (int i = 0; i < n; i++) {
			par[i] = i;
		}
	}
	int find (int x) {
		return par[x] == x ? x : par[x] = find(par[x]);
	}
	void merge (int x, int y) {
		x = find(x); y = find(y);
		if (x == y) return;
		if (x < y) swap(x, y);
		par[x] = y;
	}
} cur;
/*
p[x], y, x
if x is node with maximum u[x] / d[x], it should be placed right after p[x]
otherwise, u[x] / d[x] > u[y] / d[y], so u[x] * d[y] > u[y] * d[x], so optimal to move x
to the right

keep taking such a node and merge it with its parent
*/
struct cmp {
	bool operator()(const int &x, const int &y) const {
		if (u[x] * d[y] == u[y] * d[x]) {
			return x < y;
		}
		return u[x] * d[y] > u[y] * d[x];
	}
};
deque <int> ord[MAXN];
ll scheduling_cost(vector<int> p, vector<int> _U, vector<int> _D) {
	n = (int)p.size();
	for (int i = 0; i < n; i++) {
		u[i] = _U[i]; d[i] = _D[i];
		ord[i].push_back(i);
	}
	cur.init();
	set <int, cmp> pq;
	for (int i = 1; i < n; i++) {
		pq.insert(i);
	}
	while (!pq.empty()) {
		int k = *(pq.begin());
		assert(k != 0);
		pq.erase(k);
		p[k] = cur.find(p[k]);
		if (ord[p[k]].size() > ord[k].size()) {
			for (auto i : ord[k]) {
				ord[p[k]].push_back(i);
			}
			ord[k].clear();
		} else {
			swap(ord[p[k]], ord[k]);
			reverse(ord[k].begin(), ord[k].end());
			for (auto i : ord[k]) {
				ord[p[k]].push_front(i);
			}
		}
		pq.erase(p[k]);
		u[p[k]] += u[k]; d[p[k]] += d[k];
		if (p[k] != 0) pq.insert(p[k]);
		cur.merge(k, p[k]);
	}
	ll sum = 0, ans = 0;
	for (auto i : ord[0]) {
		sum += (ll)_D[i]; ans += (ll)_U[i] * sum;
	}
	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