Submission #308008

#	Time	Username	Problem	Language	Result	Execution time	Memory
308008		junseo	Job Scheduling (IOI19_job)	C++17	100 / 100	301 ms	20072 KiB

job

#include "job.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define rmin(r, x) r = min(r, x)
#define rmax(r, x) r = max(r, x)
#define ends ' '
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int maxn = 2e5 + 10;

struct Node {
	int i;
	ll u, d;
	Node(int i, int u, int d) : i(i), u(u), d(d) {}
	Node(void) : Node(0, 0, 0) {}
};

bool operator < (Node l, Node r) { return l.d * r.u > l.u * r.d; }

ll ans = 0;
int pa[maxn];
Node a[maxn];
priority_queue<Node> pq;

int fnd(int x) {
	if(pa[x] < 0)	return x;
	return pa[x] = fnd(pa[x]);
}

void mrge(int i, int j) {
	ans -= a[i].u * a[j].d;
	a[i].u += a[j].u;
	a[i].d += a[j].d;
}

void uni(int a, int b) {
	a = fnd(a), b = fnd(b);
	if(a == b)	return;
	pa[a] = b;
	mrge(b, a);
}

long long scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
	int n = p.size();
	memset(pa, -1, sizeof(pa));
	for(int i = 0; i < n; ++i) {
		a[i] = Node(i, u[i], d[i]);
		if(i)	pq.emplace(a[i]);
	}
	while(!pq.empty()) {
		Node t = pq.top();	pq.pop();
		if(t.i == 0 || a[t.i].u != t.u)	continue;
		uni(t.i, p[t.i]);
		pq.emplace(a[fnd(t.i)]);
	}
	ans += a[0].u * a[0].d;
	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