Submission #1193844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193844		chaeryeong	Job Scheduling (IOI19_job)	C++20	0 / 100	3101 ms	305636 KiB

job

#include "job.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 25;
vector <int> adj[MAXN];
ll u[MAXN], d[MAXN];
int n, FFFF;
deque <int> dp[MAXN];
deque <int> merge (deque <int> x, deque <int> y) {
	deque <int> ret;
	while (!x.empty() && !y.empty()) {
		if (u[x.back()] < u[y.back()]) {
			ret.push_back(x.back()); x.pop_back();
		} else {
			ret.push_back(y.back()); y.pop_back();
		}
	}
	while (!x.empty()) {
		ret.push_back(x.back()); x.pop_back();
	}
	while (!y.empty()) {
		ret.push_back(y.back()); y.pop_back();
	}
	reverse(ret.begin(), ret.end());
	return ret;
}
void dfs (int pos) {
	for (auto j : adj[pos]) {
		dfs(j);
		if (dp[j].empty()) {
			swap(dp[pos], dp[j]);
		} else dp[pos] = merge(dp[pos], dp[j]);
		dp[j].clear();
	}
	dp[pos].push_front(pos);
}
ll scheduling_cost(vector<int> p, vector<int> _U, vector<int> _D) {
	assert(!FFFF); FFFF = 1;
	n = (int)p.size();
	for (int i = 0; i < n; i++) {
		u[i] = _U[i]; d[i] = _D[i];
		if (p[i] != -1) {
			adj[p[i]].push_back(i);
		}
	}
	dfs(0);
	auto ans = dp[0];
	ll sum = 0, ret = 0;
	for (auto i : ans) {
		sum += u[i];
	}
	for (auto i : ans) {
		ret += sum * (ll)d[i];
		sum -= u[i];
	}
	return ret;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 37