Submission #202712

#	Time	Username	Problem	Language	Result	Execution time	Memory
202712		anonymous	Job Scheduling (IOI19_job)	C++14	0 / 100	35 ms	33860 KiB

job

#include "job.h"
#include <vector>
#include<queue>
#include<iostream>
#define LL long long
#define MAXN 300005
using namespace std;
struct Job {LL wt, t;};
class CompareClass {
public:
    bool operator() (Job a, Job b) {
        return(a.wt*b.t < a.t*b.wt); //wt, time
    }
};
int N, big[MAXN];
LL U[MAXN], D[MAXN], ans; //cost, time
vector<int> chd[MAXN];
priority_queue<Job, vector<Job>, CompareClass> Order[MAXN];

void dfs(int u) {
    big[u]=u;
    for (auto v: chd[u]) {
        dfs(v);
        if (Order[big[v]].size() > Order[big[u]].size()) {swap(big[u], big[v]);}
        while (Order[big[u]].size()) {
            Order[big[u]].push(Order[big[v]].top());
            Order[big[v]].pop();
        }
    }
    while (Order[big[u]].size()) {
            Job f = Order[big[u]].top();
            if (f.wt*D[u] >= f.t*U[u]) {
                ans-=f.t*U[u];
                U[u]+=f.wt, D[u]+=f.t;
                Order[big[u]].pop();
            } else {
                break;
            }
    }
    Order[big[u]].push(Job {U[u], D[u]});
}
LL scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
	N=p.size();
	for(int i=0; i<N; i++) {
        if (i) {chd[p[i]].push_back(i);}
        U[i]=u[i], D[i]=d[i];
	}
	LL time=0;
	dfs(0);
	while (Order[big[0]].size()) {
	    Job j = Order[big[0]].top();
	    Order[big[0]].pop();
        time+=j.t;
        ans+=j.wt*time;
	}
	return(ans);
}

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