Submission #1200641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200641		12345678	Job Scheduling (IOI19_job)	C++20	19 / 100	173 ms	28604 KiB

job

#include "job.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5;

struct info
{
	ll c0, c1, idx, ver;
	bool operator< (const info &o) const {return c1*o.c0<c0*o.c1;}
} lst[nx];

ll n, dsu[nx], res, t;
multiset<info> s;

int find(int x)
{
	if (dsu[x]==x) return x;
	return dsu[x]=find(dsu[x]);
}

long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
	n=p.size();
	for (int i=0; i<n; i++)
	{
		lst[i].c0=u[i];
		lst[i].c1=d[i];
		lst[i].idx=i;
		lst[i].ver=0;
		res+=u[i]*d[i];
		if (i) s.insert(lst[i]);
	}
	while (!s.empty())
	{
		auto cur=*s.begin();
		s.erase(s.begin());
		if (lst[cur.idx].ver!=cur.ver) continue;
		int pv=find(p[cur.idx]);
		dsu[cur.idx]=pv;
		res+=lst[pv].c1*cur.c0;
		lst[pv].c0+=cur.c0;
		lst[pv].c1+=cur.c1;
		lst[pv].ver=++t;
		if (pv) s.insert(lst[pv]);
	}
	return res;
}

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