oj.uz

Submission #316608

# Submission time Handle Problem Language Result Execution time Memory
316608 2020-10-26T22:53:35 Z MetB Job Scheduling (IOI19_job) C++14
0 / 100
 305 ms 71064 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;

vector <int> g[N];
int to[N], dsu[N], n, ans, dl[N];

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;
}

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 = 1; i < n; i++) {
		g[p[i]].push_back (i);
	}

	for (int i = 0; i < n; i++) {
		a[i] = {u[i], d[i]};
		to[i] = 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 (rat (u[x], d[x]) != cost) 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

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47352 KB Output is correct
2 Correct 32 ms 47352 KB Output is correct
3 Incorrect 32 ms 47352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47352 KB Output is correct
2 Correct 31 ms 47360 KB Output is correct
3 Correct 32 ms 47352 KB Output is correct
4 Incorrect 177 ms 65504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47360 KB Output is correct
2 Incorrect 32 ms 47352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47360 KB Output is correct
2 Incorrect 305 ms 71064 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47260 KB Output is correct
2 Incorrect 32 ms 47352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47352 KB Output is correct
2 Correct 32 ms 47352 KB Output is correct
3 Incorrect 32 ms 47352 KB Output isn't correct
4 Halted 0 ms 0 KB -