Submission #143972

#	Time	Username	Problem	Language	Result	Execution time	Memory
143972		nvmdava	Job Scheduling (IOI19_job)	C++17	100 / 100	531 ms	90276 KiB

job

// model_solution/job-mruxim.cpp
 
// ... ... .. ....!
// ... ....... .... ...!
 
#include<bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for(int i = 0, i##__n = (int)(n); i < i##__n; ++i)
#define fer(i, a, b) for(int i = (int)(a), i##__b = (int)(b); i < i##__b; ++i)
#define rof(i, b, a) for(int i = (int)(b), i##__a = (int)(a); i-- > i##__a; )
#define sz(x) (int((x).size()))
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define X first
#define Y second
//#define endl '\n'
 
template<class P, class Q> inline void smin(P &a, Q b) { if (b < a) a = b; }
template<class P, class Q> inline void smax(P &a, Q b) { if (a < b) a = b; }
 
typedef long long ll;
typedef pair<int, int> pii;
 
////////////////////////////////////////////////////////////////////////////////
 
const int maxn = 200000 + 100;
 
int par[maxn];
 
struct Job {
	ll urg, dur;
	bool operator<(Job j) const {
//		return urg * j.dur > j.urg * dur;
		return urg / (double)dur > j.urg / (double)j.dur;
	}
} jobs[maxn];
 
vector<int> child[maxn];
multiset<Job> path[maxn];
 
ll ans;
 
void dfs(int u) {
	int big = -1;
 
	for(int v: child[u]) {
		dfs(v);
		if(big == -1 || sz(path[v]) > sz(path[big]))
			big = v;
	}
	
	if(big != -1)
		path[u] = move(path[big]);
 
	for(int v: child[u])
		if(v != big)
			for(Job j: path[v])
				path[u].insert(j);
 
	Job cur = jobs[u];
	while(!path[u].empty() && *path[u].begin() < cur)
		ans += cur.dur * path[u].begin()->urg,
		cur.urg += path[u].begin()->urg,
		cur.dur += path[u].begin()->dur,
		path[u].erase(path[u].begin());
	path[u].insert(cur);
}
 
long long scheduling_cost(vector<int> P, vector<int> U, vector<int> D) {
	int n = sz(U);
	rep(i, n) jobs[i].urg = U[i], jobs[i].dur = D[i];
 
	int root = -1;
	rep(i, n) {
		par[i] = P[i];
		if(par[i] == -1)
			root = i;
		else
			child[par[i]].pb(i);
	}
 
	dfs(root);
 
	ll c_time = 0;
	for(Job j: path[root])
		ans += c_time * j.urg,
		c_time += j.dur;
 
	rep(i, n) ans += U[i] * D[i];
 
	return ans;
}

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