oj.uz

답안 #211014

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
211014 2020-03-19T05:41:41 Z Kevin_Zhang_TW Job Scheduling (IOI19_job) C++17
0 / 100
 22 ms 19584 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());
	ll t = 0;
	ll res = 0;
	auto dojob = [&](int a) {
		cerr << "dojob " << a << ' ' << "d, u : " << d[a] << ' ' << u[a] << '\n';
		if (did[a]) assert(false);
		did[a] = true;
		t += d[a];
		res += t * u[a];
	};
	dojob(0);
	for (int i = 0;i < v.size();++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();
}

Compilation message

job.cpp: In function 'long long int bf()':
job.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0;i < v.size();++i)
                 ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 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
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 9728 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 9728 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 21 ms 19584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 21 ms 19584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 37.0

# 결과 실행 시간 메모리 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 -