oj.uz

Submission #1015921

# Submission time Handle Problem Language Result Execution time Memory
1015921 2024-07-07T04:56:17 Z fryingduc Job Scheduling (IOI19_job) C++17
0 / 100
 6 ms 11356 KB 
#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];
    }
    dfs(0);
    info cur = {0, 0, 0};
    while(!pq[0].empty()) {
        cur.merge(pq[0].top());
        pq[0].pop();
    }
    return cur.total;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 11352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 11356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 11352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 11352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 11352 KB Output isn't correct
2 Halted 0 ms 0 KB -