제출 #660227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
660227		wenqi	Job Scheduling (IOI19_job)	C++17	100 / 100	237 ms	18752 KiB

job

// trans rights
#include <bits/extc++.h>
using namespace std;
#include "job.h"
using ll = long long;
using base = complex<double>;
#define up(k, N) for (int k = 1; k <= N; k++)
#define down(k, N) for (int k = N; k >= 1; k--)
#define f0(A) memset(A, 0, sizeof(A))
#define f3(A) memset(A, 0x3f, sizeof(A))
#define all(A) begin(A), end(A)

struct Job
{
    int id;
    ll d, u;

    bool operator < (const Job &a) const
    {
        return d * a.u > a.d * u;
    }

    bool operator != (const Job &a) const
    {
        return d != a.d or u != a.u;
    }
};

Job jobs[200069];
bool taken[200069];
int parents[200069];

int getp(int i)
{
    return i == parents[i] ? i : parents[i] = getp(parents[i]);
}

ll scheduling_cost(vector<int> P, vector<int> U, vector<int> D)
{
    int N = (int) P.size();
    priority_queue<Job> pq;
    ll ans = 0;
    for (int i = 0; i < N; i++)
    {
        Job job;
        job.id = i;
        job.u = U[i];
        job.d = D[i];
        ans += job.u * job.d;
        jobs[i] = job;
        pq.push(job);
        parents[i] = i;
    }
    while (not pq.empty())
    {
        auto job = pq.top();
        pq.pop();

        if (job != jobs[job.id] or taken[job.id])
            continue;

        int p = P[job.id];
        if (p == -1)
        {
        }else{
            auto &pj = jobs[getp(p)];
            ans += pj.d * job.u;
            pj.d += job.d;
            pj.u += job.u;
            pq.push(pj);
            parents[job.id] = getp(p);
        }
        taken[job.id] = true;
    }
    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