제출 #464773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
464773		HappyPacMan	Job Scheduling (IOI19_job)	C++14	100 / 100	265 ms	12100 KiB

job

#include "job.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 13;
int dsu[N];

int ufds(int u){
	return dsu[u] = u == dsu[u] ? u : ufds(dsu[u]);
}

struct Comp{
	const bool operator() (tuple<int,int,int> a,tuple<int,int,int> b){
		return get<0>(a) * 1LL * get<1>(b) < get<1>(a) * 1LL * get<0>(b);
	}
};

long long scheduling_cost(vector<int> p,vector<int> u,vector<int> d){
	int n = p.size();
	iota(dsu,dsu+n,0);
	long long cost = 0;
	for(int i=0;i<n;i++) cost += u[i] * 1LL * d[i];
	priority_queue<tuple<int,int,int>,vector<tuple<int,int,int> >,Comp> pq;
	for(int i=0;i<n;i++) pq.emplace(u[i],d[i],i);
	while(!pq.empty()){
		auto curr = pq.top();
		int ux = get<0>(curr);
		int id = get<2>(curr);
		pq.pop();
		if(ux != u[id]) continue;
		if(id){
			int pr = ufds(p[id]);
			cost += u[id] * 1LL * d[pr];
			dsu[id] = pr;
			u[pr] += u[id];
			d[pr] += d[id];
			pq.emplace(u[pr],d[pr],pr);
		}
	}
	return cost;
}

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