oj.uz

Submission #1010392

# Submission time Handle Problem Language Result Execution time Memory
1010392 2024-06-29T03:33:06 Z AnhPham Job Scheduling (IOI19_job) C++17
0 / 100
 57 ms 19036 KB 
#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;
    }
};
 
int 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);
    
    int 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
0 / 5.0

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

Subtask #2
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 0 ms 348 KB Output is correct
4 Incorrect 57 ms 17072 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
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 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 45 ms 19036 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 344 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 344 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -