Submission #284329

#	Time	Username	Problem	Language	Result	Execution time	Memory
284329		Pyqe	Job Scheduling (IOI19_job)	C++14	24 / 100	181 ms	41352 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,as[200069],pst[200069],dp[200069],dh[200069];
pair<long long,long long> a[200069];
vector<long long> al[200069];
bitset<200069> vtd;

bool cmp(long long x,long long y)
{
	return a[x].fr*a[y].sc<a[y].fr*a[x].sc;
}

void bd(long long x)
{
	long long i,sz=al[x].size(),l;
	
	vtd[x]=1;
	dp[x]=pst[x];
	for(i=0;i<sz;i++)
	{
		l=al[x][i];
		if(!vtd[l])
		{
			dh[l]=dh[x]+1;
			bd(l);
			dp[x]=min(dp[x],dp[l]);
		}
	}
}

bool cmp2(long long x,long long y)
{
	return mp(dp[x],dh[x])<mp(dp[y],dh[y]);
}

long long scheduling_cost(vector<int> p,vector<int> u,vector<int> d)
{
	long long i,sm=0,z=0;
	
	n=p.size();
	for(i=1;i<=n;i++)
	{
		as[i]=i;
		a[i]={d[i-1],u[i-1]};
		if(i-1)
		{
			al[p[i-1]+1].push_back(i);
		}
	}
	sort(as+1,as+n+1,cmp);
	for(i=1;i<=n;i++)
	{
		pst[as[i]]=i;
		as[i]=i;
	}
	bd(1);
	sort(as+1,as+n+1,cmp2);
	for(i=1;i<=n;i++)
	{
		sm+=a[as[i]].fr;
		z+=a[as[i]].sc*sm;
	}
	return z;
}

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