Submission #211363

#	Time	Username	Problem	Language	Result	Execution time	Memory
211363		2qbingxuan	Job Scheduling (IOI19_job)	C++14	7 / 100	268 ms	13904 KiB

job

//#include "job.h"
#include <bits/stdc++.h>
using namespace std;

long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
    int n = p.size();
    struct node {
        long long u, d;
        int id;
        bool operator<(node p)const{
            return u*p.d < d*p.u;
        }
    };
    long long ans = 0;
    vector<int> pa(n);
    iota(pa.begin(), pa.end(), 0);
    function<int(int)> anc = [&](int x){
        return x==pa[x] ? x : pa[x]=anc(pa[x]);
    };
    auto add = [&](int a, int i) {
        ans -= d[i] * u[a];
        //cerr << "ans="<<ans << '\n';
        d[a] += d[i];
        u[a] += u[i];
    };
    priority_queue<node> pq;
    for(int i = 0; i < n; i++)
        pq.push({u[i],d[i],i});
    while(pq.size()) {
        node x;
        do x=pq.top(), pq.pop(); while(pq.size() && (x.u!=u[x.id] || x.d!=d[x.id]));
        int i = x.id;
        if(p[i] == -1) continue;
        int a = anc(p[i]);
        pa[i] = a;
        add(a, i);
        //cout << "a: " << a << ' ' << u[a] << ' ' << d[a] << '\n';
        pq.push({u[a],d[a],a});
    }
    //cout << "ans = " << ans << '\n';
    ans += 1LL * u[0] * d[0];
    return ans;
}

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