답안 #211019

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
211019	2020-03-19T05:50:20 Z	Kevin_Zhang_TW	Job Scheduling (IOI19_job)	C++17	19 / 100	133 ms	23564 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';
		if (did[a]) return;
		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());
//	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();
	//cerr << "my ans is : " << res << '\n';
	//res = 0;
	//cerr << "brute force : " << bf() << '\n';
	return bf();
}

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	20 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

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	9728 KB	Output is correct
2	Correct	11 ms	9728 KB	Output is correct
3	Correct	10 ms	9856 KB	Output is correct
4	Correct	120 ms	22764 KB	Output is correct
5	Correct	121 ms	22764 KB	Output is correct
6	Correct	115 ms	22764 KB	Output is correct
7	Correct	115 ms	22764 KB	Output is correct
8	Correct	117 ms	22764 KB	Output is correct
9	Correct	120 ms	22764 KB	Output is correct
10	Correct	116 ms	22764 KB	Output is correct
11	Correct	121 ms	22764 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9728 KB	Output is correct
2	Correct	10 ms	9600 KB	Output is correct
3	Correct	10 ms	9728 KB	Output is correct
4	Correct	11 ms	9792 KB	Output is correct
5	Correct	15 ms	10496 KB	Output is correct
6	Correct	133 ms	23276 KB	Output is correct
7	Correct	127 ms	23384 KB	Output is correct
8	Correct	131 ms	23276 KB	Output is correct
9	Correct	132 ms	23276 KB	Output is correct
10	Correct	11 ms	9728 KB	Output is correct
11	Correct	10 ms	9856 KB	Output is correct
12	Correct	14 ms	10368 KB	Output is correct
13	Correct	16 ms	10496 KB	Output is correct
14	Correct	131 ms	23276 KB	Output is correct
15	Correct	130 ms	23276 KB	Output is correct
16	Correct	132 ms	23276 KB	Output is correct
17	Correct	133 ms	23564 KB	Output is correct
18	Correct	132 ms	23276 KB	Output is correct
19	Correct	127 ms	23276 KB	Output is correct
20	Correct	130 ms	23368 KB	Output is correct
21	Correct	129 ms	23404 KB	Output is correct
22	Correct	130 ms	23404 KB	Output is correct
23	Correct	129 ms	23404 KB	Output is correct
24	Correct	131 ms	23276 KB	Output is correct