Submission #707710

#	Time	Username	Problem	Language	Result	Execution time	Memory
707710		AdamGS	Job Scheduling (IOI19_job)	C++17	100 / 100	229 ms	17880 KiB

job

//#include "job.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
struct comp {
	bool operator()(pair<pair<ll,ll>,int>a, pair<pair<ll,ll>,int>b) {
		return a.st.st*b.st.nd>=a.st.nd*b.st.st;
	}
};
priority_queue<pair<pair<ll,ll>,int>,vector<pair<pair<ll,ll>,int>>,comp>q;
int F[LIM], odw[LIM], n;
ll ans, aktt;
pair<ll,ll>T[LIM];
int fnd(int x) {
	if(F[x]==x) return x;
	return F[x]=fnd(F[x]);
}
ll scheduling_cost(vector<int>P, vector<int>U, vector<int>D) {
	n=P.size();
	rep(i, n) {
		T[i]={D[i], U[i]};
		F[i]=i;
		q.push({T[i], i});
	}
	while(!q.empty()) {
		pair<ll,ll>x=q.top().st;
		int p=q.top().nd; q.pop();
		if(odw[p]) continue;
		odw[p]=1;
		if(P[p]==-1 || odw[fnd(P[p])]) {
			aktt+=x.st;
			ans+=aktt*x.nd;
			continue;
		}
		int a=fnd(P[p]);
		ans-=T[a].nd*T[p].st;
		T[a].st+=T[p].st;
		T[a].nd+=T[p].nd;
		F[p]=a;
		q.push({T[a], a});
	}
	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