Submission #417400

#	Time	Username	Problem	Language	Result	Execution time	Memory
417400		maximath_1	Job Scheduling (IOI19_job)	C++17	100 / 100	289 ms	31856 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;
	}
};

int par[200005];
int find(int nw){
	return par[nw] = (par[nw] == nw ? nw : find(par[nw]));
}

vector<int> adj[200005], ord;
void dfs(int nw){
	ord.push_back(nw);
	for(int nx : adj[nw]) dfs(nx);
}

long long scheduling_cost(vector<int> p, vector<int> u, vector<int> d){
	int n = p.size();

	vector<int> U = u, D = d;
	for(int i = 0; i < n; i ++)
		par[i] = i;

	priority_queue<job> pq;
	for(int i = 1; i < n; i ++)
		pq.push({u[i], d[i], i});

	for(; pq.size();){
		auto nw = pq.top();
		pq.pop();

		if(make_pair(nw.u, nw.d) != make_pair(U[nw.id], D[nw.id]))
			continue;

		int f = find(p[nw.id]);
		par[nw.id] = f;
		U[f] += U[nw.id];
		D[f] += D[nw.id];
		adj[f].push_back(nw.id);

		if(f) pq.push({U[f], D[f], f});
	}

	dfs(0);

	ll ans = 0ll, tim = 0ll;
	for(int i : ord){
		tim += d[i];
		ans += tim * u[i];
	}
	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