oj.uz

Submission #316638

# Submission time Handle Problem Language Result Execution time Memory
316638 2020-10-27T00:01:16 Z MetB Job Scheduling (IOI19_job) C++14
5 / 100
 263 ms 18524 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;

	for (int i = 0; i < n; i++) {
		t += d[i];
		ans += u[i] * t;
	}

	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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 50 ms 4844 KB Output is correct
6 Correct 108 ms 9064 KB Output is correct
7 Correct 181 ms 15080 KB Output is correct
8 Correct 261 ms 17768 KB Output is correct
9 Correct 263 ms 17764 KB Output is correct
10 Correct 257 ms 17764 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 262 ms 17764 KB Output is correct
13 Correct 195 ms 17756 KB Output is correct
14 Correct 219 ms 18524 KB Output is correct
15 Correct 170 ms 17792 KB Output is correct
16 Correct 202 ms 18508 KB Output is correct
17 Correct 259 ms 18044 KB Output is correct
18 Correct 260 ms 17816 KB Output is correct
19 Correct 159 ms 17756 KB Output is correct
20 Correct 140 ms 18524 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 50 ms 4844 KB Output is correct
6 Correct 108 ms 9064 KB Output is correct
7 Correct 181 ms 15080 KB Output is correct
8 Correct 261 ms 17768 KB Output is correct
9 Correct 263 ms 17764 KB Output is correct
10 Correct 257 ms 17764 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 262 ms 17764 KB Output is correct
13 Correct 195 ms 17756 KB Output is correct
14 Correct 219 ms 18524 KB Output is correct
15 Correct 170 ms 17792 KB Output is correct
16 Correct 202 ms 18508 KB Output is correct
17 Correct 259 ms 18044 KB Output is correct
18 Correct 260 ms 17816 KB Output is correct
19 Correct 159 ms 17756 KB Output is correct
20 Correct 140 ms 18524 KB Output is correct
21 Incorrect 0 ms 384 KB Output isn't correct
22 Halted 0 ms 0 KB -