답안 #316629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
316629	2020-10-26T23:18:31 Z	MetB	Job Scheduling (IOI19_job)	C++14	19 / 100	299 ms	15384 KB

#include "job.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
#define N 2000001
 
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
 
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

int merged[N], dsu[N], n, dl[N];
ll ans;

struct rat {
	ll u, d;

	rat (ll u, ll d) : u (u), d (d) {}
	rat () {}

	bool operator < (const rat& b) const {
		return b.u * d > u * b.d;
	}

	bool operator != (const rat& b) const {
		return tie (u, d) != tie (b.u, b.d);
	}
} a[N];

int find (int x) {
	if (dsu[x] == x) return x;
	return dsu[x] = find (dsu[x]);
}

void unite (int a, int b) {
	a = find (a), b = find (b);
	if (a == b) return;
	dsu[b] = a;
	merged[b] = 1;
}

ll scheduling_cost (vector <int> p, vector <int> u, vector <int> d) {
	int n = p.size ();
	priority_queue < pair <rat, int> > q;

	for (int i = 0; i < n; i++) {
		a[i] = {u[i], d[i]};
		dsu[i] = i;
		q.push ({a[i], i});
	}

	ll t = 0;

	while (!q.empty ()) {
		int x = q.top ().second;
		rat cost = q.top ().first;
		q.pop ();
		if (a[x] != cost || merged[x] || dl[x]) continue;

		if (p[x] == -1 || dl[find (p[x])]) {
			ans += (d[x] + t) * u[x];
			dl[x] = 1;
			t += d[x];
			continue;
		}
		int desc = find (p[x]);
		ans -= d[x] * u[desc];
		u[desc] += u[x];
		d[desc] += d[x];
		a[desc] = {u[desc], d[desc]};
		unite (desc, x);

		q.push ({a[desc], desc});
	}

	return ans;
}

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Incorrect	1 ms	384 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	164 ms	15076 KB	Output is correct
5	Correct	172 ms	15336 KB	Output is correct
6	Correct	167 ms	14820 KB	Output is correct
7	Correct	180 ms	15384 KB	Output is correct
8	Correct	170 ms	14692 KB	Output is correct
9	Correct	173 ms	15332 KB	Output is correct
10	Correct	165 ms	15336 KB	Output is correct
11	Correct	160 ms	14692 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	7 ms	1280 KB	Output is correct
6	Correct	181 ms	15204 KB	Output is correct
7	Correct	176 ms	15204 KB	Output is correct
8	Correct	172 ms	15332 KB	Output is correct
9	Correct	171 ms	15204 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	512 KB	Output is correct
12	Correct	6 ms	1220 KB	Output is correct
13	Correct	7 ms	1280 KB	Output is correct
14	Correct	175 ms	15336 KB	Output is correct
15	Correct	172 ms	14952 KB	Output is correct
16	Correct	182 ms	15332 KB	Output is correct
17	Correct	169 ms	15332 KB	Output is correct
18	Correct	164 ms	14564 KB	Output is correct
19	Correct	169 ms	15204 KB	Output is correct
20	Correct	167 ms	14948 KB	Output is correct
21	Correct	169 ms	14692 KB	Output is correct
22	Correct	180 ms	15004 KB	Output is correct
23	Correct	173 ms	15332 KB	Output is correct
24	Correct	171 ms	14692 KB	Output is correct