Submission #417387

#	Time	Username	Problem	Language	Result	Execution time	Memory
417387		maximath_1	Job Scheduling (IOI19_job)	C++17	24 / 100	153 ms	19204 KiB

job

#include "job.h"
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
#define ll long long

struct job{
	int u, d, id;
	bool operator < (const job &rhs) const{
		return d * 1ll * rhs.u > u * 1ll * rhs.d;
	}
};

vector<int> adj[200005];

long long scheduling_cost(vector<int> p, vector<int> u, vector<int> d){
	int n = p.size();
	for(int i = 1; i < n; i ++)
		adj[p[i]].push_back(i);


	priority_queue<job> pq;
	pq.push({u[0], d[0], 0});

	ll ans = 0ll, tim = 0ll;
	for(; pq.size();){
		auto nw = pq.top(); pq.pop();
		tim += d[nw.id]; ans += tim * 1ll * u[nw.id];
		for(int nx : adj[nw.id])
			pq.push({u[nx], d[nx], nx});
	}

	return ans;
}

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