oj.uz

Submission #211042

# Submission time Handle Problem Language Result Execution time Memory
211042 2020-03-19T06:06:40 Z Kevin_Zhang_TW Job Scheduling (IOI19_job) C++17
44 / 100
 3000 ms 29876 KB 
#include "job.h"
#include <bits/extc++.h>
#include <vector>
#define pb emplace_back
const int maxn = 200010;
using ll = long long;
using namespace std;
int deg[maxn], togo[maxn], tl, n;
ll res;
vector<int> edge[maxn], sorted[maxn];
ll p[maxn], u[maxn], d[maxn];
struct cmp {
	bool operator()(int a, int b) const {
		return d[a] * u[b] > d[b] * u[a];
	}
};
void sub_merge(int a, int b) {
	res -= (ll)d[b] * u[a];
	d[a] += d[b];
	u[a] += u[b];
}
void get_ans() {
	res = 0;
	for (int i = 0;i < n;++i) {
		int now = togo[i];
		for (int u : edge[now]) {
			if (sorted[u].size() > sorted[now].size()) swap(sorted[u], sorted[now]);
			int a = sorted[now].size();
			//for (int s : sorted[u]) sorted[now].pb(s);
			sorted[now].insert(sorted[now].end(), sorted[u].begin(), sorted[u].end());
			inplace_merge(sorted[now].begin(), sorted[now].begin()+a, sorted[now].end(), cmp());
		}
		//sort(sorted[now].begin(), sorted[now].end(), cmp());
		while (sorted[now].size() && cmp()(now, sorted[now].back())) {
			sub_merge(now, sorted[now].back());
			sorted[now].pop_back();
		}
		sorted[now].pb(now);
//		if (now)
//			sorted[now].pb(now);
	}
	auto &v = sorted[0];
	//sort(v.begin(), v.end(), cmp());
	ll t = 0;
	auto dojob = [&](int a) {
		//cerr << "dojob " << a << ' ' << "d, u : " << d[a] << ' ' << u[a] << '\n';
		t += d[a];
		res += t * u[a];
	};
	//dojob(0);
	while (v.size()) {
		dojob(v.back());
		v.pop_back();
	}
}
//long long bf() {
//	static bool did[maxn];
//	auto &v = edge[0];
//	sort(v.begin(), v.end(), cmp());
//	for (int u : v)assert(u);
//	ll t = 0;
//	ll res = 0;
//	auto dojob = [&](int a) {
//		t += d[a];
//		res += t * u[a];
//	};
//	dojob(0);
//	for (int i = (int)v.size()-1;i >= 0;--i)
//		dojob(v[i]);
//	return res;
//}
long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
	n = p.size();
	for (int i = 1;i < n;++i) edge[p[i]].pb(i);
	for (int i = 1;i < n;++i) ++deg[ p[i] ];
	for (int i = 0;i < n;++i) if (deg[i] == 0)
		togo[tl++] = i;
	for (int i = 0;i < n;++i) {
		int now = togo[i];
		if (now == 0) {
			assert(n-1 == i);
		   	break;
		}
		if ( --deg[ p[now] ] == 0) togo[tl++] = p[now];
	}
	for (int i = 0;i < n;++i) 
		::p[i] = p[i], ::u[i] = u[i], ::d[i] = d[i];
	get_ans();
	return res;
	//cerr << "my ans is : " << res << '\n';
	//res = 0;
	//cerr << "brute force : " << bf() << '\n';
	//return bf();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 11 ms 9728 KB Output is correct
4 Correct 10 ms 9856 KB Output is correct
5 Correct 38 ms 14840 KB Output is correct
6 Correct 68 ms 19320 KB Output is correct
7 Correct 100 ms 23536 KB Output is correct
8 Correct 121 ms 27768 KB Output is correct
9 Correct 122 ms 27768 KB Output is correct
10 Correct 124 ms 27964 KB Output is correct
11 Correct 10 ms 9728 KB Output is correct
12 Correct 141 ms 27768 KB Output is correct
13 Correct 123 ms 27900 KB Output is correct
14 Correct 124 ms 27896 KB Output is correct
15 Correct 129 ms 27896 KB Output is correct
16 Correct 132 ms 27896 KB Output is correct
17 Correct 127 ms 27656 KB Output is correct
18 Correct 125 ms 27640 KB Output is correct
19 Correct 160 ms 27640 KB Output is correct
20 Correct 131 ms 28784 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Execution timed out 3076 ms 29008 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 12 ms 9856 KB Output is correct
5 Correct 66 ms 10872 KB Output is correct
6 Execution timed out 3078 ms 29876 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 129 ms 28024 KB Output is correct
3 Correct 127 ms 27864 KB Output is correct
4 Correct 128 ms 27896 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 11 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 12 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 10 ms 9728 KB Output is correct
11 Correct 11 ms 9728 KB Output is correct
12 Correct 10 ms 9728 KB Output is correct
13 Correct 10 ms 9728 KB Output is correct
14 Correct 11 ms 9728 KB Output is correct
15 Correct 10 ms 9728 KB Output is correct
16 Correct 12 ms 9728 KB Output is correct
17 Correct 11 ms 9728 KB Output is correct

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 11 ms 9728 KB Output is correct
4 Correct 10 ms 9856 KB Output is correct
5 Correct 38 ms 14840 KB Output is correct
6 Correct 68 ms 19320 KB Output is correct
7 Correct 100 ms 23536 KB Output is correct
8 Correct 121 ms 27768 KB Output is correct
9 Correct 122 ms 27768 KB Output is correct
10 Correct 124 ms 27964 KB Output is correct
11 Correct 10 ms 9728 KB Output is correct
12 Correct 141 ms 27768 KB Output is correct
13 Correct 123 ms 27900 KB Output is correct
14 Correct 124 ms 27896 KB Output is correct
15 Correct 129 ms 27896 KB Output is correct
16 Correct 132 ms 27896 KB Output is correct
17 Correct 127 ms 27656 KB Output is correct
18 Correct 125 ms 27640 KB Output is correct
19 Correct 160 ms 27640 KB Output is correct
20 Correct 131 ms 28784 KB Output is correct
21 Correct 10 ms 9728 KB Output is correct
22 Correct 10 ms 9728 KB Output is correct
23 Correct 10 ms 9728 KB Output is correct
24 Execution timed out 3076 ms 29008 KB Time limit exceeded
25 Halted 0 ms 0 KB -