oj.uz

Submission #866437

# Submission time Handle Problem Language Result Execution time Memory
866437 2023-10-26T07:27:44 Z SorahISA Job Scheduling (IOI19_job) C++17
40 / 100
 523 ms 262144 KB 
#include "job.h"
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

struct Job {
    int64 u, d, id;
    Job(int _u, int _d, int _id) : u(_u), d(_d), id(_id) {}
    bool operator < (const Job &rhs) const {
        return d * rhs.u < rhs.d * u;
    }
};

int64 scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
    int N = p.size();
    vector<vector<int>> ch(N);
    for (int i = 1; i < N; ++i) ch[p[i]].emplace_back(i);
    
    multiset<Job> jobs;
    for (int i = 0; i < N; ++i) jobs.emplace(u[i], d[i], i);
    
    int64 tim = 0, ans = 0;
    while (jobs.size()) {
        
        Job job = *begin(jobs);
        jobs.erase(begin(jobs));
        
        // cerr << "(" << job.u << ", " << job.d << ", " << job.id << ")\n";
        if (u[job.id] != job.u or d[job.id] != job.d) continue;
        // cerr << "(" << job.u << ", " << job.d << ", " << job.id << ")\n";
        
        if (p[job.id] == -1) {
            ans += job.u * (tim += job.d);
            for (int x : ch[job.id]) p[x] = -1;
            ch[job.id].clear();
        }
        else {
            ans -= u[p[job.id]] * job.d;
            int64 new_u = u[p[job.id]] + job.u;
            int64 new_d = d[p[job.id]] + job.d;
            
            // if (ch[p[job.id]].size() <= ch[job.id].size()) {
            //     u[job.id] = new_u, d[job.id] = new_d;
            //     for (int x : ch[p[job.id]]) {if (x != job.id) ch[job.id].emplace_back(x), p[x] = job.id;}
            //     ch[p[job.id]].clear();
            //     if (p[p[job.id]] != -1) ch[p[p[job.id]]].emplace_back(job.id);
            //     p[job.id] = p[p[job.id]];
            //     jobs.emplace(u[job.id], d[job.id], job.id);
            // }
            // else {
                u[p[job.id]] = new_u, d[p[job.id]] = new_d;
                for (int x : ch[job.id]) ch[p[job.id]].emplace_back(x), p[x] = p[job.id];
                ch[job.id].clear();
                jobs.emplace(u[p[job.id]], d[p[job.id]], p[job.id]);
            // }
        }
    }
    
    return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 88 ms 51668 KB Output is correct
6 Correct 259 ms 167164 KB Output is correct
7 Runtime error 456 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 128 ms 22940 KB Output is correct
5 Correct 127 ms 22972 KB Output is correct
6 Correct 130 ms 22980 KB Output is correct
7 Correct 123 ms 23132 KB Output is correct
8 Correct 119 ms 23116 KB Output is correct
9 Correct 164 ms 23064 KB Output is correct
10 Correct 109 ms 23060 KB Output is correct
11 Correct 117 ms 23112 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Correct 118 ms 23128 KB Output is correct
7 Correct 114 ms 22980 KB Output is correct
8 Correct 119 ms 22984 KB Output is correct
9 Correct 156 ms 22944 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 3 ms 1372 KB Output is correct
13 Correct 4 ms 1540 KB Output is correct
14 Correct 123 ms 23008 KB Output is correct
15 Correct 119 ms 22956 KB Output is correct
16 Correct 152 ms 23036 KB Output is correct
17 Correct 122 ms 22984 KB Output is correct
18 Correct 127 ms 22980 KB Output is correct
19 Correct 114 ms 23096 KB Output is correct
20 Correct 118 ms 23148 KB Output is correct
21 Correct 126 ms 23240 KB Output is correct
22 Correct 115 ms 23092 KB Output is correct
23 Correct 139 ms 22984 KB Output is correct
24 Correct 119 ms 23044 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 523 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 432 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 436 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 88 ms 51668 KB Output is correct
6 Correct 259 ms 167164 KB Output is correct
7 Runtime error 456 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -