Submission #211020

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
211020	2020-03-19T05:50:44 Z	Kevin_Zhang_TW	Job Scheduling (IOI19_job)	C++17	19 / 100	134 ms	21868 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() {
	for (int i = 0;i < n;++i) {
		int now = togo[i];
		assert(now || i == n-1);
		for (int u : edge[now]) {
			if (sorted[u].size() > sorted[now].size()) swap(sorted[u], sorted[now]);
			int a = sorted[now].size();
			sorted[now].insert(sorted[now].begin(), sorted[u].begin(), sorted[u].end());
			inplace_merge(sorted[now].begin(), sorted[now].begin()+a, 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);
	}
	auto &v = sorted[0];
	ll t = 0;
	auto dojob = [&](int a) {
		cerr << "dojob " << a << ' ' << "d, u : " << d[a] << ' ' << u[a] << '\n';
		t += d[a];
		res += t * u[a];
	};
	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) {
		//cerr << "dojob " << a << ' ' << "d, u : " << d[a] << ' ' << u[a] << '\n';
		did[a] = true;
		t += d[a];
		res += t * u[a];
	};
	dojob(0);
	for (int i = (int)v.size()-1;i >= 0;--i)
		dojob(v[i]), assert(edge[v[i]].empty());
	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();
	//cerr << "my ans is : " << res << '\n';
	//res = 0;
	//cerr << "brute force : " << bf() << '\n';
	return bf();
}

Compilation message

job.cpp: In function 'long long int bf()':
job.cpp:51:14: warning: variable 'did' set but not used [-Wunused-but-set-variable]
  static bool did[maxn];
              ^~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	22 ms	19584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #2
7.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	11 ms	9728 KB	Output is correct
4	Correct	111 ms	21740 KB	Output is correct
5	Correct	120 ms	21752 KB	Output is correct
6	Correct	110 ms	21744 KB	Output is correct
7	Correct	110 ms	21740 KB	Output is correct
8	Correct	113 ms	21740 KB	Output is correct
9	Correct	118 ms	21676 KB	Output is correct
10	Correct	113 ms	21868 KB	Output is correct
11	Correct	115 ms	21740 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	9728 KB	Output is correct
2	Correct	11 ms	9728 KB	Output is correct
3	Correct	11 ms	9728 KB	Output is correct
4	Correct	11 ms	9856 KB	Output is correct
5	Correct	15 ms	10496 KB	Output is correct
6	Correct	127 ms	21740 KB	Output is correct
7	Correct	125 ms	21792 KB	Output is correct
8	Correct	124 ms	21740 KB	Output is correct
9	Correct	124 ms	21740 KB	Output is correct
10	Correct	11 ms	9728 KB	Output is correct
11	Correct	11 ms	9856 KB	Output is correct
12	Correct	18 ms	10368 KB	Output is correct
13	Correct	16 ms	10496 KB	Output is correct
14	Correct	127 ms	21740 KB	Output is correct
15	Correct	121 ms	21740 KB	Output is correct
16	Correct	125 ms	21740 KB	Output is correct
17	Correct	128 ms	21740 KB	Output is correct
18	Correct	134 ms	21740 KB	Output is correct
19	Correct	127 ms	21740 KB	Output is correct
20	Correct	123 ms	21740 KB	Output is correct
21	Correct	126 ms	21868 KB	Output is correct
22	Correct	121 ms	21740 KB	Output is correct
23	Correct	126 ms	21740 KB	Output is correct
24	Correct	125 ms	21720 KB	Output is correct