Submission #373254

# Submission time Handle Problem Language Result Execution time Memory
373254 2021-03-03T23:42:17 Z MilosMilutinovic Job Scheduling (IOI19_job) C++14
7 / 100
119 ms 43628 KB
#include "job.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

const int mxN=2e5;
int n;
vector<int> adj[mxN], p, u, d;
bool was[mxN];
ll ans=0;

struct cmp{
	bool operator()(int x, int y) {
		return d[x]*u[y]>d[y]*u[x];
	}
};

priority_queue<int, vector<int>, cmp> q[mxN];

void merge(int x, int y) {
	d[x]+=d[y];
	u[x]+=u[y];	
}

void dfs(int x) {
	assert(x>=0&&x<n);
	for(int v:adj[x])
		dfs(v), q[x].push(v);
	while(!q[x].empty()) {
		int y=q[x].top();
		if(d[y]*u[x]>d[x]*u[y])
			break;
		was[y]=true;
		q[x].pop();
		ans-=d[y]*u[x];
		merge(x, y);
		if((int)q[x].size()<(int)q[y].size())
			swap(q[x], q[y]);
		while(!q[y].empty())
			q[x].push(q[y].top()), q[y].pop();
	}	
}

ll scheduling_cost(vector<int> p1, vector<int> u1, vector<int> d1) {
	p=p1, u=u1, d=d1;
	n = (int) p.size();
	for(int i=1; i<n; ++i) 
		adj[p1[i]].pb(i);
	dfs(0);
	vector<int> j;
	for(int i=0; i<n; ++i)
		if(!was[i])
			j.pb(i);
	sort(j.rbegin(), j.rend(), [&](int x, int y) {
		return d[x]*u[y]>d[y]*u[x];
	});
	ll t=0;
	for(int i:j)
		t+=d[i], ans+=u[i]*t;
	return ans;
}
# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Correct 8 ms 11244 KB Output is correct
3 Incorrect 8 ms 11244 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Correct 8 ms 11244 KB Output is correct
3 Correct 9 ms 11244 KB Output is correct
4 Correct 114 ms 23392 KB Output is correct
5 Correct 114 ms 23392 KB Output is correct
6 Correct 113 ms 23392 KB Output is correct
7 Correct 114 ms 23392 KB Output is correct
8 Correct 109 ms 23240 KB Output is correct
9 Correct 113 ms 23392 KB Output is correct
10 Correct 111 ms 23392 KB Output is correct
11 Correct 109 ms 23264 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Correct 8 ms 11244 KB Output is correct
3 Correct 8 ms 11244 KB Output is correct
4 Correct 9 ms 11520 KB Output is correct
5 Incorrect 15 ms 12012 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Incorrect 119 ms 43628 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Correct 9 ms 11244 KB Output is correct
3 Incorrect 8 ms 11244 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Correct 8 ms 11244 KB Output is correct
3 Incorrect 8 ms 11244 KB Output isn't correct
4 Halted 0 ms 0 KB -