oj.uz

Submission #146753

# Submission time Handle Problem Language Result Execution time Memory
146753 2019-08-26T01:01:10 Z qkxwsm Job Scheduling (IOI19_job) C++14
19 / 100
 297 ms 64428 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;
typedef pair<pll, int> ppi;

int N;
int parent[MAXN], link[MAXN];
bitset<MAXN> taken;
vi edge[MAXN];
pii arr[MAXN];

struct cmp1
{
	bool operator() (const ppi &a, const ppi &b) const
	{
		if (a.fi.fi * b.fi.se != a.fi.se * b.fi.fi)
		return a.fi.fi * b.fi.se < a.fi.se * b.fi.fi;
		return a.se < b.se;
	}
};

set<ppi, cmp1> s;
ll ans = 0, t = 0;

bool cmp(pll a, pll b)
{
	return a.fi * b.se > a.se * b.fi;
}
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);
		arr[i] = {u[i], d[i]};
		s.insert({{arr[i].fi, arr[i].se}, i});
		link[i] = parent[i];
		ans += arr[i].fi * arr[i].se;
		// cerr << "parent " << parent[i] << endl;
	}
	taken[N] = true;
	FOR(i, 0, N)
	{
		int u = (prev(s.end())) -> se;
		s.erase(prev(s.end()));
		if (taken[link[u]])
		{
			ans += arr[u].fi * t;
			t += arr[u].se;
			taken[u] = true;
			continue;
			//cool gg
		}
		for (int v : edge[u])
		{
			link[v] = link[u];
		}
		int v = link[u];
		s.erase(s.find({{arr[v].fi, arr[v].se}, v}));
		ans += arr[v].se * arr[u].fi;
		arr[v].fi += arr[u].fi;
		arr[v].se += arr[u].se;
		s.insert({{arr[v].fi, arr[v].se}, v});
	}
	return ans;
	//yo uwant to take stuff with high fi/se first
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Runtime error 15 ms 10232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 245 ms 27980 KB Output is correct
5 Correct 241 ms 27884 KB Output is correct
6 Correct 238 ms 27984 KB Output is correct
7 Correct 253 ms 27992 KB Output is correct
8 Correct 261 ms 27984 KB Output is correct
9 Correct 253 ms 28012 KB Output is correct
10 Correct 247 ms 28140 KB Output is correct
11 Correct 241 ms 28012 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct
3 Correct 7 ms 4984 KB Output is correct
4 Correct 8 ms 5112 KB Output is correct
5 Correct 16 ms 6136 KB Output is correct
6 Correct 261 ms 28652 KB Output is correct
7 Correct 261 ms 28524 KB Output is correct
8 Correct 258 ms 28472 KB Output is correct
9 Correct 272 ms 28524 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 7 ms 5240 KB Output is correct
12 Correct 13 ms 6008 KB Output is correct
13 Correct 14 ms 6136 KB Output is correct
14 Correct 287 ms 28524 KB Output is correct
15 Correct 287 ms 28516 KB Output is correct
16 Correct 272 ms 28496 KB Output is correct
17 Correct 272 ms 28528 KB Output is correct
18 Correct 271 ms 28468 KB Output is correct
19 Correct 281 ms 28548 KB Output is correct
20 Correct 270 ms 28584 KB Output is correct
21 Correct 250 ms 28524 KB Output is correct
22 Correct 277 ms 28528 KB Output is correct
23 Correct 268 ms 28656 KB Output is correct
24 Correct 278 ms 28524 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Runtime error 297 ms 64428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Runtime error 13 ms 9976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Runtime error 15 ms 10232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -