제출 #802883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802883		Ahmed57	Job Scheduling (IOI19_job)	C++17	100 / 100	167 ms	29508 KiB

job

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

#define ll long long

const int mxN=2e5;
int n, nxt[mxN], ta[mxN];
vector<int> o;
ll u2[mxN], d2[mxN];

struct cmp {
	bool operator()(const int &a, const int &b) {
		return d2[a]*u2[b]>d2[b]*u2[a];
	}
};
priority_queue<int, vector<int>, cmp> c[mxN];

void dfs(int u) {
	o.push_back(u);
	for(; c[u].size(); c[u].pop())
		dfs(c[u].top());
}

ll scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
	n=p.size();
	memset(nxt, -1, 4*n);
	iota(ta, ta+n, 0);
	for(int i=n-1; ~i; --i) {
		u2[i]=u[i];
		d2[i]=d[i];
		while(c[i].size()) {
			int u=c[i].top();
			if(cmp()(u, i))
				break;
			c[i].pop();
			nxt[ta[i]]=u;
			ta[i]=ta[u];
			u2[i]+=u2[u];
			d2[i]+=d2[u];
			if(c[i].size()<c[u].size())
				swap(c[i], c[u]);
			for(; c[u].size(); c[u].pop())
				c[i].push(c[u].top());
		}
		if(i)
			c[p[i]].push(i);
	}
	dfs(0);
	sort(o.begin(), o.end(), cmp());
	ll t=0, ans=0;
	for(int i=o.size()-1; ~i; --i) {
		for(int j=o[i]; ~j; j=nxt[j]) {
			t+=d[j];
			ans+=t*u[j];
		}
	}
	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