Submission #145746

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
145746	2019-08-21T05:41:06 Z	qkxwsm	Job Scheduling (IOI19_job)	C++14	19 / 100	250 ms	31240 KB

#include "job.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 200013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef pair<ld, int> pdi;

int N;
int parent[MAXN], link[MAXN];
pll arr[MAXN];
vi edge[MAXN], tail[MAXN];
vi ord;
ll ans = 0;
priority_queue<pdi> pq;

ll scheduling_cost(vi p, vi u, vi d)
{
	N = SZ(p);
	// cerr << "HI\n";
	FOR(i, 0, N)
	{
		parent[i] = p[i];
		if (i == 0) parent[i] = N;
		else edge[parent[i]].PB(i);
		link[i] = parent[i];
		arr[i] = {u[i], d[i]};
		// cerr << "parent " << parent[i] << endl;
	}
	FOR(i, 0, N)
	{
		pq.push({1.0 * u[i] / d[i], i});
	}
	while(!pq.empty())
	{
		auto p = pq.top(); pq.pop();
		int u = p.se;
		// cerr << u << " -> " << link[u] << endl;
		if (link[u] == N)
		{
			ord.PB(u);
			ord.insert(ord.end(), ALL(tail[u]));
		}
		else
		{
			tail[link[u]].PB(u);
			tail[link[u]].insert(tail[link[u]].end(), ALL(tail[u]));
		}
		for (int v : edge[u])
		{
			link[v] = link[u];
		}
	}
	ll t = 0;
	for (int u : ord)
	{
		// cerr << "u = " << u << endl;
		t += arr[u].se;
		ans += t * arr[u].fi;
	}
	return ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9720 KB	Output is correct
2	Correct	11 ms	9720 KB	Output is correct
3	Correct	10 ms	9720 KB	Output is correct
4	Correct	195 ms	30048 KB	Output is correct
5	Correct	211 ms	30516 KB	Output is correct
6	Correct	195 ms	30080 KB	Output is correct
7	Correct	206 ms	30560 KB	Output is correct
8	Correct	195 ms	30052 KB	Output is correct
9	Correct	201 ms	29916 KB	Output is correct
10	Correct	208 ms	29916 KB	Output is correct
11	Correct	198 ms	30020 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9720 KB	Output is correct
2	Correct	12 ms	9700 KB	Output is correct
3	Correct	13 ms	9720 KB	Output is correct
4	Correct	10 ms	9848 KB	Output is correct
5	Correct	18 ms	11064 KB	Output is correct
6	Correct	206 ms	30504 KB	Output is correct
7	Correct	203 ms	30564 KB	Output is correct
8	Correct	233 ms	30928 KB	Output is correct
9	Correct	203 ms	30808 KB	Output is correct
10	Correct	10 ms	9720 KB	Output is correct
11	Correct	12 ms	10104 KB	Output is correct
12	Correct	17 ms	10908 KB	Output is correct
13	Correct	18 ms	11064 KB	Output is correct
14	Correct	214 ms	31056 KB	Output is correct
15	Correct	228 ms	30556 KB	Output is correct
16	Correct	212 ms	31100 KB	Output is correct
17	Correct	207 ms	31112 KB	Output is correct
18	Correct	197 ms	30556 KB	Output is correct
19	Correct	209 ms	30668 KB	Output is correct
20	Correct	211 ms	31184 KB	Output is correct
21	Correct	216 ms	30560 KB	Output is correct
22	Correct	207 ms	31240 KB	Output is correct
23	Correct	250 ms	31108 KB	Output is correct
24	Correct	204 ms	30564 KB	Output is correct