oj.uz

Submission #350053

# Submission time Handle Problem Language Result Execution time Memory
350053 2021-01-19T00:27:55 Z thecodingwizard Job Scheduling (IOI19_job) C++17
0 / 100
 8 ms 11264 KB 
#include "job.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define all(x) x.begin(), x.end()
#define ii pair<int, int>
#define f first
#define s second
#define mp make_pair

vector<int> adj[200000];
vector<ll> p, u, d;

struct cmp {
    // returns true if i should go after j
    bool operator()(int i, int j) {
        return d[i]*u[j]>=d[j]*u[i];
    }
};
priority_queue<int, vector<int>, cmp> children[200000];

bool merged[200000];

ll ans = 0;
void dfs(int node) {
    for (int child : adj[node]) {
        dfs(child);
    }
    for (int child : adj[node]) {
        children[node].push(child);
    }
    while (!children[node].empty()) {
        if (cmp()(node, children[node].top())) {
            int toMerge = children[node].top();
            children[node].pop();
            ans -= d[toMerge]*u[node];
            d[node] += d[toMerge];
            u[node] += u[toMerge];
            if (children[node].size() < children[toMerge].size()) {
                swap(children[node], children[toMerge]);
            }
            assert(children[node].size() >= children[toMerge].size());
            while (children[toMerge].size()) {
                children[node].push(children[toMerge].top());
                children[toMerge].pop();
            }
            merged[toMerge] = true;
        } else {
            break;
        }
    }
}

long long scheduling_cost(std::vector<int> _p, std::vector<int> _u, std::vector<int> _d) {
    int n = p.size();
    for (int i = 0; i < n; i++) {
        p.pb(_p[i]);
        u.pb(_u[i]);
        d.pb(_d[i]);
    }

    for (int i = 1; i < n; i++) {
        adj[p[i]].pb(i);
    }

    dfs(0);

    vector<int> indices;
    for (int i = 0; i < n; i++) {
        if (!merged[i]) {
            indices.pb(i);
        }
    }
    sort(all(indices), cmp());
    reverse(all(indices));

    ll curTime = 0;

    for (auto x : indices) {
        curTime += d[x];
        ans += curTime*u[x];
    }

    return ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 37.0

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