Submission #587358

#	Time	Username	Problem	Language	Result	Execution time	Memory
587358		blue	Job Scheduling (IOI19_job)	C++17	100 / 100	676 ms	23984 KiB

job

#include "job.h"
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
#define sz(x) int(x.size())

ll res = 0;

const int mx = 200'000;

struct dsu
{
	vi par = vi(1+mx);
	vi st = vi(1+mx, 1);
	vi peak = vi(1+mx);

	dsu()
	{
		for(int i = 0; i <= mx; i++)
		{
			par[i] = i;
			peak[i] = i;
		}
	}

	int root(int u)
	{
		if(par[u] == u) return u;
		else return (par[u] = root(par[u]));
	}

	int getpeak(int u)
	{
		return peak[root(u)];
	}

	bool join(int u, int v, int p)
	{
		u = root(u);
		v = root(v);

		if(u == v)
			return 0;

		if(st[u] < st[v])
			swap(u, v);

		par[v] = u;
		st[u] += st[v];
		peak[u] = p;

		return 1;
	}
};	

int n;

vi p;
vll u, d;

struct temple
{
	int i;
};

bool operator < (temple A, temple B)
{
	if(d[A.i]*u[B.i] == d[B.i]*u[A.i])
		return A.i < B.i;
	else
		return d[A.i]*u[B.i] < d[B.i]*u[A.i];
}

ll scheduling_cost(vi p_, vi u_, vi d_) 
{
	p = p_;
	n = sz(p);

	u = d = vll(n);
	for(int i = 0; i < n; i++)
	{
		u[i] = u_[i];
		d[i] = d_[i];
	}

	dsu ds;

	for(int i = 0; i < n; i++)
		res += u[i]*d[i];

	set<temple> S;
	for(int i = 1; i < n; i++)
		S.insert(temple{i});	

	//combined values are stored at the paek

	for(int t = 0; t < n-1; t++)
	{
		int a = S.begin()->i;
		S.erase(S.begin());

		int pa = ds.getpeak(a);

		int b = p[pa];
		int pb = ds.getpeak(b);

		res += d[pb] * u[pa];

		
		ds.join(pa, pb, pb);

		if(pb == 0)
		{
			d[pb] += d[pa];
			u[pb] += u[pa];
		}
		else
		{
			S.erase(temple{pb});

			d[pb] += d[pa];
			u[pb] += u[pa];

			S.insert(temple{pb});
		}
	}


	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