Submission #350048

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
350048	2021-01-19T00:18:14 Z	thecodingwizard	Job Scheduling (IOI19_job)	C++17	7 / 100	129 ms	43648 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<int> 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) {
    p = _p, u = _u, d = _d;

    int n = p.size();
    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	Correct	8 ms	11264 KB	Output is correct
2	Correct	8 ms	11244 KB	Output is correct
3	Incorrect	8 ms	11244 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	11244 KB	Output is correct
2	Correct	8 ms	11244 KB	Output is correct
3	Correct	8 ms	11244 KB	Output is correct
4	Correct	108 ms	23392 KB	Output is correct
5	Correct	112 ms	23392 KB	Output is correct
6	Correct	122 ms	23264 KB	Output is correct
7	Correct	109 ms	23392 KB	Output is correct
8	Correct	108 ms	23264 KB	Output is correct
9	Correct	109 ms	23392 KB	Output is correct
10	Correct	111 ms	23392 KB	Output is correct
11	Correct	108 ms	23136 KB	Output is correct

Subtask #3
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	11244 KB	Output is correct
2	Correct	8 ms	11244 KB	Output is correct
3	Correct	8 ms	11244 KB	Output is correct
4	Correct	8 ms	11372 KB	Output is correct
5	Incorrect	13 ms	11884 KB	Output isn't correct
6	Halted	0 ms	0 KB	-