Submission #284568

#	Time	Username	Problem	Language	Result	Execution time	Memory
284568		Pyqe	Job Scheduling (IOI19_job)	C++14	100 / 100	468 ms	100728 KiB

job

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

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n,z=0,a[200069],wg[200069],dsu[200069],cc[200069];
vector<long long> al[200069];

struct cmp
{
	bool operator()(pair<long long,long long> x,pair<long long,long long> y)
	{
		return x.fr*y.sc<y.fr*x.sc;
	}
};

multiset<pair<long long,long long>,cmp> ms[200069];
multiset<pair<long long,long long>,cmp>::iterator it;

long long fd(long long x)
{
	if(dsu[x]!=x)
	{
		dsu[x]=fd(dsu[x]);
	}
	return dsu[x];
}

void jo(long long x,long long y)
{
	x=fd(x);
	y=fd(y);
	if(cc[x]<cc[y])
	{
		swap(x,y);
	}
	for(it=ms[y].begin();it!=ms[y].end();it++)
	{
		ms[x].insert(*it);
	}
	dsu[y]=x;
	cc[x]+=cc[y];
}

void dfs(long long x)
{
	long long i,sz=al[x].size(),l;
	
	dsu[x]=x;
	cc[x]=1;
	for(i=0;i<sz;i++)
	{
		l=al[x][i];
		dfs(l);
		jo(x,l);
	}
	for(it=ms[fd(x)].begin();it!=ms[fd(x)].end();)
	{
		if(a[x]*it->sc<=it->fr*wg[x])
		{
			break;
		}
		z-=it->fr*wg[x];
		a[x]+=it->fr;
		wg[x]+=it->sc;
		it++;
		ms[fd(x)].erase(prev(it));
	}
	ms[fd(x)].insert({a[x],wg[x]});
}

long long scheduling_cost(vector<int> pr,vector<int> wgg,vector<int> aa)
{
	long long i,sm=0;
	
	n=pr.size();
	for(i=1;i<=n;i++)
	{
		a[i]=aa[i-1];
		wg[i]=wgg[i-1];
		if(i-1)
		{
			al[pr[i-1]+1].push_back(i);
		}
	}
	dfs(1);
	for(it=ms[fd(1)].begin();it!=ms[fd(1)].end();it++)
	{
		sm+=it->fr;
		z+=it->sc*sm;
	}
	return z;
}

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