oj.uz

Submission #1010395

# Submission time Handle Problem Language Result Execution time Memory
1010395 2024-06-29T03:35:19 Z AnhPham Job Scheduling (IOI19_job) C++17
24 / 100
 73 ms 19416 KB 
#include "job.h"
#include <bits/stdc++.h>
 
#ifdef OP_DEBUG
    #include <algo/debug.h>
#else
    #define debug(...) 26
#endif
 
using namespace std;
 
// #define int 	long long
#define sz(v)   (int)(v).size()
#define all(v)  (v).begin(), (v).end()
#define TcT     template <class T
 
const   int     MOD = (int)1e9 + 7, INF = (int)4e18 + 18;
 
TcT>            bool minimize(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }
TcT>            bool maximize(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }
 
/* [Pham Hung Anh - 12I - Tran Hung Dao High School for Gifted Student] */
 
struct Info {
    int id;
    int w, t;
    bool operator < (const Info &other) const {
        return w * other.t < other.w * t;
    }
};
 
long long scheduling_cost(vector <int> p, vector <int> u, vector <int> d) {
    int n = sz(p);
    vector <vector <int>> adj(n);
    for (int i = 1; i < n; ++i)
        adj[p[i]].emplace_back(i);
    
    long long tot_time = 0, ans = 0;
    priority_queue <Info> pq; pq.push({ 0, u[0], d[0] });
    while (sz(pq)) {
        Info job = pq.top(); pq.pop();  
        tot_time += d[job.id];
        ans += tot_time * u[job.id];
        for (int v : adj[job.id])
            pq.push({ v, u[v], d[v] });
    }
 
    return ans;
}
 
// void solve() {
//     int n; cin >> n;
 
//     vector <int> P(n), W(n), T(n);
//     for (int &p : P)
//         cin >> p;
    
//     for (int &w : W)
//         cin >> w;
    
//     for (int &t : T)
//         cin >> t;
    
//     vector <vector <int>> adj(n);
//     for (int i = 1; i < n; ++i)
//         adj[P[i]].emplace_back(i);
    
//     int tot_time = 0, ans = 0;
//     priority_queue <Info> pq; pq.push({ 0, W[0], T[0] });
//     while (sz(pq)) {
//         Info job = pq.top(); pq.pop();  
//         tot_time += T[job.id];
//         ans += tot_time * W[job.id];
//         for (int v : adj[job.id])
//             pq.push({ v, W[v], T[v] });
//     }
 
//     cout << ans << '\n';
// }

Subtask #1
5.0 / 5.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 0 ms 604 KB Output is correct
5 Correct 11 ms 5116 KB Output is correct
6 Correct 21 ms 9544 KB Output is correct
7 Correct 34 ms 14324 KB Output is correct
8 Correct 47 ms 19144 KB Output is correct
9 Correct 51 ms 19168 KB Output is correct
10 Correct 47 ms 19124 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 43 ms 19032 KB Output is correct
13 Correct 57 ms 19416 KB Output is correct
14 Correct 45 ms 19260 KB Output is correct
15 Correct 43 ms 19028 KB Output is correct
16 Correct 48 ms 19028 KB Output is correct
17 Correct 45 ms 19124 KB Output is correct
18 Correct 41 ms 19032 KB Output is correct
19 Correct 47 ms 19128 KB Output is correct
20 Correct 41 ms 19144 KB Output is correct

Subtask #2
7.0 / 7.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 56 ms 15700 KB Output is correct
5 Correct 58 ms 16068 KB Output is correct
6 Correct 73 ms 16180 KB Output is correct
7 Correct 59 ms 16064 KB Output is correct
8 Correct 57 ms 17124 KB Output is correct
9 Correct 60 ms 15980 KB Output is correct
10 Correct 62 ms 16064 KB Output is correct
11 Correct 57 ms 17088 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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 1372 KB Output is correct
6 Correct 65 ms 17596 KB Output is correct
7 Correct 59 ms 16576 KB Output is correct
8 Correct 60 ms 17600 KB Output is correct
9 Correct 62 ms 16584 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 1116 KB Output is correct
13 Correct 3 ms 1372 KB Output is correct
14 Correct 62 ms 16688 KB Output is correct
15 Correct 62 ms 16580 KB Output is correct
16 Correct 60 ms 18108 KB Output is correct
17 Correct 69 ms 16632 KB Output is correct
18 Correct 61 ms 17600 KB Output is correct
19 Correct 59 ms 16696 KB Output is correct
20 Correct 61 ms 18112 KB Output is correct
21 Correct 67 ms 16588 KB Output is correct
22 Correct 65 ms 16576 KB Output is correct
23 Correct 62 ms 17860 KB Output is correct
24 Correct 61 ms 16576 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 Incorrect 42 ms 15964 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 37.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 0 ms 604 KB Output is correct
5 Correct 11 ms 5116 KB Output is correct
6 Correct 21 ms 9544 KB Output is correct
7 Correct 34 ms 14324 KB Output is correct
8 Correct 47 ms 19144 KB Output is correct
9 Correct 51 ms 19168 KB Output is correct
10 Correct 47 ms 19124 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 43 ms 19032 KB Output is correct
13 Correct 57 ms 19416 KB Output is correct
14 Correct 45 ms 19260 KB Output is correct
15 Correct 43 ms 19028 KB Output is correct
16 Correct 48 ms 19028 KB Output is correct
17 Correct 45 ms 19124 KB Output is correct
18 Correct 41 ms 19032 KB Output is correct
19 Correct 47 ms 19128 KB Output is correct
20 Correct 41 ms 19144 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 56 ms 15700 KB Output is correct
25 Correct 58 ms 16068 KB Output is correct
26 Correct 73 ms 16180 KB Output is correct
27 Correct 59 ms 16064 KB Output is correct
28 Correct 57 ms 17124 KB Output is correct
29 Correct 60 ms 15980 KB Output is correct
30 Correct 62 ms 16064 KB Output is correct
31 Correct 57 ms 17088 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 3 ms 1372 KB Output is correct
37 Correct 65 ms 17596 KB Output is correct
38 Correct 59 ms 16576 KB Output is correct
39 Correct 60 ms 17600 KB Output is correct
40 Correct 62 ms 16584 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 2 ms 1116 KB Output is correct
44 Correct 3 ms 1372 KB Output is correct
45 Correct 62 ms 16688 KB Output is correct
46 Correct 62 ms 16580 KB Output is correct
47 Correct 60 ms 18108 KB Output is correct
48 Correct 69 ms 16632 KB Output is correct
49 Correct 61 ms 17600 KB Output is correct
50 Correct 59 ms 16696 KB Output is correct
51 Correct 61 ms 18112 KB Output is correct
52 Correct 67 ms 16588 KB Output is correct
53 Correct 65 ms 16576 KB Output is correct
54 Correct 62 ms 17860 KB Output is correct
55 Correct 61 ms 16576 KB Output is correct
56 Correct 0 ms 344 KB Output is correct
57 Incorrect 42 ms 15964 KB Output isn't correct
58 Halted 0 ms 0 KB -