Submission #718301

#	Time	Username	Problem	Language	Result	Execution time	Memory
718301		potato167	Job Scheduling (IOI19_job)	C++17	100 / 100	317 ms	20788 KiB

job

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


long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
	int n=p.size();
	struct _job
	{
		long long cost;
		long long time;
		int ind;
	};
	std::vector<int> par(n);
	std::vector<_job> val(n);
	long long ans=0;
	for(int i=0;i<n;i++){
		par[i]=i;
		val[i].cost=(long long)u[i];
		val[i].time=(long long)d[i];
		val[i].ind=i;
		ans+=val[i].cost*val[i].time;
	}
	auto concat_job=[&](_job &l,_job r)->void{
		ans+=l.time*r.cost;
		l.time+=r.time;
		l.cost+=r.cost;
	};
	auto comp_job=[&](_job l,_job r)->bool{
		return l.cost*r.time<l.time*r.cost;
	};
	auto root=[&](auto self,int a)->int{
		if(a==par[a]) return a;
		par[a]=self(self,par[a]);
		return par[a];
	};
	std::priority_queue<_job,std::vector<_job>,std::function<bool(_job,_job)>> pq(comp_job);
	int t=-1;
	for(int i=0;i<n;i++){
		if(p[i]==-1) t=i;
	}
	std::vector<int> seen(n);
	for(int i=0;i<n;i++){
		if(i!=t){
			pq.push(val[i]);
		}
	}
	while(!pq.empty()){
		_job tmp=pq.top();
		pq.pop();
		if(seen[tmp.ind]) continue;
		if(val[tmp.ind].cost!=tmp.cost||val[tmp.ind].time!=tmp.time) continue;
		seen[tmp.ind]=1;
		par[tmp.ind]=p[tmp.ind];
		int r=root(root,tmp.ind);
		concat_job(val[r],tmp);
		if(r!=t) pq.push(val[r]);
	}
	return ans;
}

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