Submission #316761

#	Time	Username	Problem	Language	Result	Execution time	Memory
316761		MetB	Job Scheduling (IOI19_job)	C++14	100 / 100	256 ms	18688 KiB

job

#include "job.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
#define N 2000001
 
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
 
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
 
int merged[N], dsu[N], n, dl[N];
ll ans;
 
struct rat {
	ll u, d;
 
	rat (ll u, ll d) : u (u), d (d) {}
	rat () {}
 
	bool operator < (const rat& b) const {
		return b.u * d > u * b.d;
	}
 
	bool operator != (const rat& b) const {
		return tie (u, d) != tie (b.u, b.d);
	}
} a[N];
 
int find (int x) {
	if (dsu[x] == x) return x;
	return dsu[x] = find (dsu[x]);
}
 
void unite (int a, int b) {
	a = find (a), b = find (b);
	if (a == b) return;
	dsu[b] = a;
	merged[b] = 1;
}
 
ll scheduling_cost (vector <int> p, vector <int> u, vector <int> d) {
	int n = p.size ();
	
	p.resize (n);
	u.resize (n);
	d.resize (n);
	
	priority_queue < pair <rat, int> > q;
 
	for (int i = 0; i < n; i++) {
		a[i] = {u[i], d[i]};
		dsu[i] = i;
		q.push ({a[i], i});
	}
 
	ll t = 0;
 
	while (!q.empty ()) {
		ll x = q.top ().second;
		rat cost = q.top ().first;
		q.pop ();
		if (a[x] != cost || merged[x] || dl[x]) continue;
 
		if (p[x] == -1 || dl[find (p[x])]) {
			ans += (d[x] + t) * u[x];
			dl[x] = 1;
			t += d[x];
			continue;
		}
		int desc = find (p[x]);
		ans -= (ll) d[x] * u[desc];
		u[desc] += u[x];
		d[desc] += d[x];
		a[desc] = {u[desc], d[desc]};
		unite (desc, x);
 
		q.push ({a[desc], desc});
	}
 
	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