Submission #202626

#	Time	Username	Problem	Language	Result	Execution time	Memory
202626		anonymous	Job Scheduling (IOI19_job)	C++14	5 / 100	203 ms	79864 KiB

job

#include "job.h"
#include <vector>
#include<set>
#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];
multiset<Job, CompareClass> Order[MAXN];

int dfs(int u) {
    big[u]=u;
    for (auto v: chd[u]) {
        int p = dfs(v);
        while (Order[p].size()) {
            Job f = *Order[p].begin();
            if (f.wt*D[u] >= f.t*U[u]) {
                ans-=f.t*U[u];
                U[u]+=f.wt, D[u]+=f.t;
                Order[p].erase(Order[p].begin());
            } else {
                break;
            }
        }
    }
    Order[big[u]].insert(Job {U[u], D[u]});
    for (auto v: chd[u]) {
        if (Order[big[v]].size() > Order[big[u]].size()) {
            swap(big[u], big[v]);
        }
        for (Job j: Order[big[v]]) {
            Order[big[u]].insert(j);
        }
    }
    return(big[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;
	int ptr = dfs(0);
	for (Job j: Order[ptr]) {
        time+=j.t;
        ans+=j.wt*time;
	}
	return(ans);
}

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