Submission #145739

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
145739	2019-08-21T05:30:24 Z	qkxwsm	Job Scheduling (IOI19_job)	C++14	19 / 100	246 ms	31188 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 = " << u << endl;
		if (link[u] == N)
		{
			ord.PB(u);
			ord.insert(ord.end(), ALL(tail[u]));
		}
		else
		{
			tail[link[u]].PB(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	Incorrect	11 ms	9720 KB	Output isn't correct
2	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	10 ms	9720 KB	Output is correct
3	Correct	11 ms	9720 KB	Output is correct
4	Correct	192 ms	30048 KB	Output is correct
5	Correct	198 ms	30548 KB	Output is correct
6	Correct	194 ms	30048 KB	Output is correct
7	Correct	203 ms	30620 KB	Output is correct
8	Correct	194 ms	30096 KB	Output is correct
9	Correct	204 ms	29924 KB	Output is correct
10	Correct	197 ms	30020 KB	Output is correct
11	Correct	192 ms	30052 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	9720 KB	Output is correct
2	Correct	11 ms	9720 KB	Output is correct
3	Correct	11 ms	9720 KB	Output is correct
4	Correct	14 ms	9848 KB	Output is correct
5	Correct	18 ms	11064 KB	Output is correct
6	Correct	205 ms	30556 KB	Output is correct
7	Correct	235 ms	30560 KB	Output is correct
8	Correct	225 ms	30964 KB	Output is correct
9	Correct	204 ms	30856 KB	Output is correct
10	Correct	11 ms	9720 KB	Output is correct
11	Correct	14 ms	9976 KB	Output is correct
12	Correct	20 ms	10936 KB	Output is correct
13	Correct	21 ms	11064 KB	Output is correct
14	Correct	206 ms	31116 KB	Output is correct
15	Correct	201 ms	30560 KB	Output is correct
16	Correct	200 ms	31188 KB	Output is correct
17	Correct	246 ms	31096 KB	Output is correct
18	Correct	198 ms	30556 KB	Output is correct
19	Correct	199 ms	30644 KB	Output is correct
20	Correct	232 ms	31056 KB	Output is correct
21	Correct	200 ms	30556 KB	Output is correct
22	Correct	203 ms	31060 KB	Output is correct
23	Correct	203 ms	31060 KB	Output is correct
24	Correct	199 ms	30608 KB	Output is correct