Submission #314853

#	Time	Username	Problem	Language	Result	Execution time	Memory
314853		blue	Job Scheduling (IOI19_job)	C++17	24 / 100	314 ms	36572 KiB

job

#include "job.h"
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

struct job
{
    long long u;
    long long d;
    int i;
    vector<int> children;
};

bool operator < (job A, job B)
{
    if(A.u*B.d == B.u*A.d) return A.i < B.i;
    return A.u*B.d > B.u*A.d;
}

long long scheduling_cost(vector<int> p, vector<int> u, vector<int> d)
{
    long long res = 0;
    int n = p.size();

    job J[n];
    vector<int> v;
    for(int i = 0; i < n; i++)
    {
        J[i] = job{u[i], d[i], i, v};
        if(i > 0) J[p[i]].children.push_back(i);
    }

    long long t = 0;

    set<job> S;
    S.insert(J[0]);

    job j;

    while(!S.empty())
    {
        j = *S.begin();
        S.erase(S.begin());
        for(int k: j.children) S.insert(J[k]);
        t += j.d;
        res += t * j.u;
    }

	return res;
}

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