Submission #1015922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015922		fryingduc	Job Scheduling (IOI19_job)	C++17	100 / 100	179 ms	62276 KiB

job

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

const int maxn = 2e5 + 5;
int n, w[maxn], t[maxn], p[maxn];
vector<int> g[maxn];

struct info {
    long long w, t, total;
    void merge(const info &o) {
        total += o.total + t * o.w;
        w += o.w;
        t += o.t;
    }
    bool operator<(const info &o) const {
        return w * o.t > o.w * t;
    }
    bool operator>(const info &o) const {
        return w * o.t < o.w * t;
    }
};

priority_queue<info, vector<info>, greater<info>> pq[maxn];
void dfs(int u) {
    for(auto v:g[u]) {
        dfs(v);
        if(pq[u].size() < pq[v].size()) {
            swap(pq[u], pq[v]);
        }
        while(!pq[v].empty()) {
            pq[u].push(pq[v].top());
            pq[v].pop();
        }
    }
    info cur = {w[u], t[u], 1ll * w[u] * t[u]};
    while(!pq[u].empty()) {
        info top = pq[u].top();
        if(cur < top) break;
        cur.merge(pq[u].top());
        pq[u].pop();
    }
    pq[u].push(cur);
}
long long scheduling_cost(vector<int> _p, vector<int> _w, vector<int> _t) {
    n = _p.size();
    for(int i = 0; i < n; ++i) {
        p[i] = _p[i];
        w[i] = _w[i];
        t[i] = _t[i];
        
        if(p[i] != -1) {
            g[p[i]].push_back(i);
        }
    }
    dfs(0);
    info cur = {0, 0, 0};
    while(!pq[0].empty()) {
        cur.merge(pq[0].top());
        pq[0].pop();
    }
    return cur.total;
}

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