제출 #316608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
316608		MetB	Job Scheduling (IOI19_job)	C++14	0 / 100	305 ms	71064 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;

vector <int> g[N];
int to[N], dsu[N], n, ans, dl[N];

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;
}

ll scheduling_cost (vector <int> p, vector <int> u, vector <int> d) {
	int n = p.size ();
	priority_queue < pair <rat, int> > q;
	
	for (int i = 1; i < n; i++) {
		g[p[i]].push_back (i);
	}

	for (int i = 0; i < n; i++) {
		a[i] = {u[i], d[i]};
		to[i] = i, dsu[i] = i;
		q.push ({a[i], i});
	}

	ll t = 0;

	while (!q.empty ()) {
		int x = q.top ().second;
		rat cost = q.top ().first;
		q.pop ();
		if (rat (u[x], d[x]) != cost) 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 -= 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: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 37