Submission #202713

#	Time	Username	Problem	Language	Result	Execution time	Memory
202713		anonymous	Job Scheduling (IOI19_job)	C++14	100 / 100	418 ms	98680 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];
 
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]);}
        for (Job j: Order[big[v]]) {
            Order[big[u]].insert(j);
        }
    }
    while (Order[big[u]].size()) {
            Job f = *Order[big[u]].begin();
            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]].erase(Order[big[u]].begin());
            } else {
                break;
            }
    }
    Order[big[u]].insert(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);
	for (Job j: Order[big[0]]) {
        time+=j.t;
        ans+=j.wt*time;
	}
	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