oj.uz

Submission #146757

# Submission time Handle Problem Language Result Execution time Memory
146757 2019-08-26T01:09:02 Z qkxwsm Job Scheduling (IOI19_job) C++14
19 / 100
 331 ms 69292 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];
pll arr[MAXN];

struct cmp
{
	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, cmp> s;
ll ans = 0, t = 0;

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 5112 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 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 265 ms 29136 KB Output is correct
5 Correct 258 ms 29288 KB Output is correct
6 Correct 250 ms 29296 KB Output is correct
7 Correct 270 ms 29220 KB Output is correct
8 Correct 254 ms 29208 KB Output is correct
9 Correct 261 ms 29396 KB Output is correct
10 Correct 260 ms 29164 KB Output is correct
11 Correct 262 ms 29292 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5084 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5116 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 14 ms 6264 KB Output is correct
6 Correct 293 ms 29164 KB Output is correct
7 Correct 265 ms 29320 KB Output is correct
8 Correct 247 ms 29452 KB Output is correct
9 Correct 289 ms 29420 KB Output is correct
10 Correct 7 ms 5116 KB Output is correct
11 Correct 7 ms 5208 KB Output is correct
12 Correct 14 ms 6184 KB Output is correct
13 Correct 14 ms 6264 KB Output is correct
14 Correct 260 ms 29316 KB Output is correct
15 Correct 275 ms 29648 KB Output is correct
16 Correct 254 ms 29580 KB Output is correct
17 Correct 276 ms 29596 KB Output is correct
18 Correct 278 ms 29676 KB Output is correct
19 Correct 331 ms 29676 KB Output is correct
20 Correct 269 ms 29676 KB Output is correct
21 Correct 277 ms 29808 KB Output is correct
22 Correct 277 ms 29548 KB Output is correct
23 Correct 279 ms 29676 KB Output is correct
24 Correct 295 ms 29548 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Runtime error 313 ms 69292 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 4988 KB Output is correct
2 Runtime error 13 ms 9936 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 5112 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 -