Submission #874818

#	Time	Username	Problem	Language	Result	Execution time	Memory
874818		rainboy	Job Scheduling (IOI19_job)	C++17	100 / 100	303 ms	48168 KiB

job

#include "job.h"
#include <cstdlib>
#include <vector>

using namespace std;

typedef vector<int> vi;

const int N = 200000;

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int n;
int *ej[N], eo[N];

void append(int i, int j) {
	int o = eo[i]++;
	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

long long cross(int x1, int y1, int x2, int y2) {
	return (long long) x1 * y2 - (long long) x2 * y1;
}

int xx[N], yy[N];

int compare(int i, int j) {
	long long c = cross(xx[i], yy[i], xx[j], yy[j]);
	return c != 0 ? (c < 0 ? -1 : 1) : i - j;
}

int zz[N + 1], ll[N + 1], rr[N + 1], ii[N + 1], u_, l_, r_;

int node(int i) {
	static int _ = 1;
	zz[_] = rand_();
	ll[_] = rr[_] = 0;
	ii[_] = i;
	return _++;
}

void split(int u, int i) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	int c = compare(ii[u], i);
	if (c < 0) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

int first(int u) {
	return ll[u] == 0 ? u : first(ll[u]);
}

int remove_first(int u) {
	if (ll[u] == 0)
		return rr[u];
	ll[u] = remove_first(ll[u]);
	return u;
}

int merge_(int u, int v) {
	while (v) {
		int w = first(v); v = remove_first(v); ll[w] = rr[w] = 0;
		split(u, ii[w]);
		u = merge(merge(l_, w), r_);
	}
	return u;
}

int sz[N], uu[N]; long long ans;

void dfs(int i) {
	sz[i] = 1, uu[i] = 0;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		dfs(j);
		uu[i] = sz[i] > sz[j] ? merge_(uu[i], uu[j]) : merge_(uu[j], uu[i]);
		sz[i] += sz[j];
	}
	while (uu[i]) {
		int w = first(uu[i]);
		if (compare(i, ii[w]) < 0)
			break;
		uu[i] = remove_first(uu[i]);
		ans += (long long) xx[i] * yy[ii[w]];
		xx[i] += xx[ii[w]], yy[i] += yy[ii[w]];
	}
	uu[i] = merge(node(i), uu[i]);
}

long long scheduling_cost(vi pp, vi yy_, vi xx_) {
	n = pp.size();
	for (int i = 0; i < n; i++)
		xx[i] = xx_[i], yy[i] = yy_[i];
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
	for (int i = 1; i < n; i++)
		append(pp[i], i);
	ans = 0;
	for (int i = 0; i < n; i++)
		ans += (long long) xx[i] * yy[i];
	dfs(0);
	int x = 0;
	while (uu[0]) {
		int w = first(uu[0]); uu[0] = remove_first(uu[0]);
		ans += (long long) x * yy[ii[w]], x += xx[ii[w]];
	}
	for (int i = 0; i < n; i++)
		free(ej[i]);
	return ans;
}

Compilation message (stderr)

job.cpp: In function 'void append(int, int)':
job.cpp:22:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   22 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

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