Submission #211029

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
211029	2020-03-19T05:59:54 Z	Kevin_Zhang_TW	Job Scheduling (IOI19_job)	C++17	19 / 100	142 ms	29480 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];
		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();
			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();
}

Compilation message

job.cpp: In function 'long long int bf()':
job.cpp:58:14: warning: unused variable 'did' [-Wunused-variable]
  static bool did[maxn];
              ^~~
job.cpp: At global scope:
job.cpp:58:14: warning: 'did' defined but not used [-Wunused-variable]

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	11 ms	9728 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	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	122 ms	29292 KB	Output is correct
5	Correct	122 ms	29292 KB	Output is correct
6	Correct	119 ms	29292 KB	Output is correct
7	Correct	119 ms	29292 KB	Output is correct
8	Correct	120 ms	29292 KB	Output is correct
9	Correct	119 ms	29292 KB	Output is correct
10	Correct	120 ms	29292 KB	Output is correct
11	Correct	124 ms	29420 KB	Output is correct

Subtask #3
12.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	11 ms	9856 KB	Output is correct
5	Correct	16 ms	10752 KB	Output is correct
6	Correct	141 ms	29292 KB	Output is correct
7	Correct	142 ms	29292 KB	Output is correct
8	Correct	130 ms	29292 KB	Output is correct
9	Correct	134 ms	29292 KB	Output is correct
10	Correct	10 ms	9728 KB	Output is correct
11	Correct	11 ms	9984 KB	Output is correct
12	Correct	15 ms	10752 KB	Output is correct
13	Correct	16 ms	10880 KB	Output is correct
14	Correct	129 ms	29292 KB	Output is correct
15	Correct	130 ms	29480 KB	Output is correct
16	Correct	132 ms	29292 KB	Output is correct
17	Correct	130 ms	29292 KB	Output is correct
18	Correct	132 ms	29292 KB	Output is correct
19	Correct	132 ms	29292 KB	Output is correct
20	Correct	133 ms	29292 KB	Output is correct
21	Correct	133 ms	29292 KB	Output is correct
22	Correct	133 ms	29292 KB	Output is correct
23	Correct	136 ms	29292 KB	Output is correct
24	Correct	136 ms	29292 KB	Output is correct