Submission #331185

#	Time	Username	Problem	Language	Result	Execution time	Memory
331185		ttnhuy313	Job Scheduling (IOI19_job)	C++14	5 / 100	128 ms	56940 KiB

job

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 2e5 + 5;
int n, sum_cost[N], sum_d[N], dp[N], cost[N], d[N];
vector <int> adj[N];

void dfs(int u) {
	sum_cost[u] = cost[u];
	sum_d[u] = d[u];
	vector <int> V; V.clear();
	for (int v : adj[u]) {
		V.push_back(v);
		dfs(v);
		sum_cost[u] += sum_cost[v];
		sum_d[u] += sum_d[v];
	}
	sort(V.begin(), V.end(), [](int i, int j) {
		return 1.0 * sum_d[i] / sum_cost[i] < 1.0 * sum_d[j] * sum_cost[j];
	});
	dp[u] = d[u] * cost[u];
	int pre = d[u];
	for (int v : V) {
		dp[u] += dp[v] + pre * sum_cost[v];
		pre += sum_d[v];
	}
}

int scheduling_cost(vector <int32_t> p, vector <int32_t> c, vector <int32_t> time) {	
	n = p.size();
	for (int i = 0; i < n; ++i) {
		cost[i] = c[i];
		d[i] = time[i];
	}
	for (int i = 1; i < n; ++i) {
		adj[p[i]].push_back(i);
	}
	dfs(0);
	return dp[0];
}

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