oj.uz

Submission #350060

# Submission time Handle Problem Language Result Execution time Memory
350060 2021-01-19T00:31:39 Z thecodingwizard Job Scheduling (IOI19_job) C++14
56 / 100
 158 ms 53704 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]);
            }
            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
5.0 / 5.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 11500 KB Output is correct
5 Correct 37 ms 21472 KB Output is correct
6 Correct 65 ms 31700 KB Output is correct
7 Correct 93 ms 41924 KB Output is correct
8 Correct 124 ms 52168 KB Output is correct
9 Correct 121 ms 52168 KB Output is correct
10 Correct 124 ms 52168 KB Output is correct
11 Correct 8 ms 11244 KB Output is correct
12 Correct 121 ms 52168 KB Output is correct
13 Correct 123 ms 52168 KB Output is correct
14 Correct 146 ms 52168 KB Output is correct
15 Correct 121 ms 52168 KB Output is correct
16 Correct 126 ms 52168 KB Output is correct
17 Correct 121 ms 52168 KB Output is correct
18 Correct 121 ms 52224 KB Output is correct
19 Correct 121 ms 52384 KB Output is correct
20 Correct 132 ms 53704 KB Output is correct

Subtask #2
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 Runtime error 158 ms 49076 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Correct 9 ms 11244 KB Output is correct
3 Correct 8 ms 11264 KB Output is correct
4 Correct 8 ms 11372 KB Output is correct
5 Correct 13 ms 12008 KB Output is correct
6 Correct 118 ms 24264 KB Output is correct
7 Correct 118 ms 24264 KB Output is correct
8 Correct 118 ms 24264 KB Output is correct
9 Correct 116 ms 24328 KB Output is correct
10 Correct 8 ms 11244 KB Output is correct
11 Correct 9 ms 11372 KB Output is correct
12 Correct 12 ms 12012 KB Output is correct
13 Correct 13 ms 12008 KB Output is correct
14 Correct 118 ms 24264 KB Output is correct
15 Correct 115 ms 24264 KB Output is correct
16 Correct 127 ms 24264 KB Output is correct
17 Correct 116 ms 24264 KB Output is correct
18 Correct 115 ms 24152 KB Output is correct
19 Correct 116 ms 24276 KB Output is correct
20 Correct 118 ms 24264 KB Output is correct
21 Correct 116 ms 24392 KB Output is correct
22 Correct 115 ms 24264 KB Output is correct
23 Correct 115 ms 24264 KB Output is correct
24 Correct 116 ms 24112 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Correct 122 ms 42832 KB Output is correct
3 Correct 121 ms 42848 KB Output is correct
4 Correct 122 ms 42952 KB Output is correct

Subtask #5
21.0 / 21.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 11244 KB Output is correct
5 Correct 8 ms 11244 KB Output is correct
6 Correct 9 ms 11244 KB Output is correct
7 Correct 8 ms 11244 KB Output is correct
8 Correct 8 ms 11244 KB Output is correct
9 Correct 8 ms 11244 KB Output is correct
10 Correct 8 ms 11244 KB Output is correct
11 Correct 8 ms 11244 KB Output is correct
12 Correct 8 ms 11244 KB Output is correct
13 Correct 8 ms 11244 KB Output is correct
14 Correct 8 ms 11244 KB Output is correct
15 Correct 8 ms 11244 KB Output is correct
16 Correct 8 ms 11244 KB Output is correct
17 Correct 8 ms 11244 KB Output is correct

Subtask #6
0 / 37.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 11500 KB Output is correct
5 Correct 37 ms 21472 KB Output is correct
6 Correct 65 ms 31700 KB Output is correct
7 Correct 93 ms 41924 KB Output is correct
8 Correct 124 ms 52168 KB Output is correct
9 Correct 121 ms 52168 KB Output is correct
10 Correct 124 ms 52168 KB Output is correct
11 Correct 8 ms 11244 KB Output is correct
12 Correct 121 ms 52168 KB Output is correct
13 Correct 123 ms 52168 KB Output is correct
14 Correct 146 ms 52168 KB Output is correct
15 Correct 121 ms 52168 KB Output is correct
16 Correct 126 ms 52168 KB Output is correct
17 Correct 121 ms 52168 KB Output is correct
18 Correct 121 ms 52224 KB Output is correct
19 Correct 121 ms 52384 KB Output is correct
20 Correct 132 ms 53704 KB Output is correct
21 Correct 8 ms 11244 KB Output is correct
22 Correct 8 ms 11244 KB Output is correct
23 Correct 8 ms 11244 KB Output is correct
24 Runtime error 158 ms 49076 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -