oj.uz

답안 #350054

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
350054 2021-01-19T00:29:23 Z thecodingwizard Job Scheduling (IOI19_job) C++14
56 / 100
 165 ms 56904 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
5.0 / 5.0

# 결과 실행 시간 메모리 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 9 ms 11500 KB Output is correct
5 Correct 38 ms 22260 KB Output is correct
6 Correct 68 ms 33236 KB Output is correct
7 Correct 100 ms 44356 KB Output is correct
8 Correct 135 ms 55368 KB Output is correct
9 Correct 129 ms 55368 KB Output is correct
10 Correct 130 ms 55368 KB Output is correct
11 Correct 8 ms 11248 KB Output is correct
12 Correct 129 ms 55368 KB Output is correct
13 Correct 126 ms 55368 KB Output is correct
14 Correct 131 ms 55368 KB Output is correct
15 Correct 128 ms 55368 KB Output is correct
16 Correct 133 ms 55388 KB Output is correct
17 Correct 132 ms 55368 KB Output is correct
18 Correct 129 ms 55368 KB Output is correct
19 Correct 126 ms 55368 KB Output is correct
20 Correct 138 ms 56904 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Correct 8 ms 11244 KB Output is correct
3 Correct 8 ms 11328 KB Output is correct
4 Runtime error 165 ms 48968 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

# 결과 실행 시간 메모리 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 10 ms 11372 KB Output is correct
5 Correct 13 ms 12008 KB Output is correct
6 Correct 127 ms 26568 KB Output is correct
7 Correct 122 ms 26568 KB Output is correct
8 Correct 121 ms 26568 KB Output is correct
9 Correct 122 ms 26568 KB Output is correct
10 Correct 8 ms 11264 KB Output is correct
11 Correct 9 ms 11372 KB Output is correct
12 Correct 12 ms 12140 KB Output is correct
13 Correct 13 ms 12136 KB Output is correct
14 Correct 123 ms 26696 KB Output is correct
15 Correct 127 ms 26568 KB Output is correct
16 Correct 124 ms 26568 KB Output is correct
17 Correct 124 ms 26568 KB Output is correct
18 Correct 125 ms 26440 KB Output is correct
19 Correct 126 ms 26568 KB Output is correct
20 Correct 122 ms 26568 KB Output is correct
21 Correct 125 ms 26440 KB Output is correct
22 Correct 121 ms 26568 KB Output is correct
23 Correct 121 ms 26568 KB Output is correct
24 Correct 123 ms 26440 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Correct 127 ms 42824 KB Output is correct
3 Correct 128 ms 46024 KB Output is correct
4 Correct 126 ms 46024 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 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 8 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 11372 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 11372 KB Output is correct
15 Correct 8 ms 11244 KB Output is correct
16 Correct 8 ms 11244 KB Output is correct
17 Correct 10 ms 11372 KB Output is correct

Subtask #6
0 / 37.0

# 결과 실행 시간 메모리 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 9 ms 11500 KB Output is correct
5 Correct 38 ms 22260 KB Output is correct
6 Correct 68 ms 33236 KB Output is correct
7 Correct 100 ms 44356 KB Output is correct
8 Correct 135 ms 55368 KB Output is correct
9 Correct 129 ms 55368 KB Output is correct
10 Correct 130 ms 55368 KB Output is correct
11 Correct 8 ms 11248 KB Output is correct
12 Correct 129 ms 55368 KB Output is correct
13 Correct 126 ms 55368 KB Output is correct
14 Correct 131 ms 55368 KB Output is correct
15 Correct 128 ms 55368 KB Output is correct
16 Correct 133 ms 55388 KB Output is correct
17 Correct 132 ms 55368 KB Output is correct
18 Correct 129 ms 55368 KB Output is correct
19 Correct 126 ms 55368 KB Output is correct
20 Correct 138 ms 56904 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 11328 KB Output is correct
24 Runtime error 165 ms 48968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -