oj.uz

Submission #1010605

# Submission time Handle Problem Language Result Execution time Memory
1010605 2024-06-29T08:26:54 Z AnhPham Job Scheduling (IOI19_job) C++17
0 / 100
 1 ms 604 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; }

void solve();

// int32_t main() {
//     cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false);
//     int testcases = 1;

// #define TC 0
//     if (TC) { cin >> testcases; } for (; testcases--;) { solve(); }
// }

/* [Pham Hung Anh - 12I - Tran Hung Dao High School for Gifted Student] */

long long scheduling_cost(vector <int> p, vector <int> u, vector <int> d) {
    vector <vector <int>> adj(sz(p));
    for (int i = 1; i < sz(p); ++i)
        adj[p[i]].emplace_back(i);
    
    auto Merge = [&](vector<int> l, vector<int> r) {
        int n = sz(l), m = sz(r);
        vector <long long> pfa(n + 1), pfb(m + 1);
        for (int i = 0; i < n; i++)
            pfa[i + 1] = pfa[i] + d[l[i]];

        for (int i = 0; i < m; i++)
            pfb[i + 1] = pfb[i] + d[r[i]];
        
        vector <vector <long long>> dp(n + 1, vector <long long> (m + 1, INF)); dp[0][0] = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i < n)
                    minimize(dp[i + 1][j], dp[i][j] + (pfa[i + 1] + pfb[j]) * u[l[i]]);

                if (j < m)
                    minimize(dp[i][j + 1], dp[i][j] + (pfa[i] + pfb[j + 1]) * u[r[j]]);
            }
        }

        vector <int> merged;
        while (n > 0 || m > 0) {
            if (n > 0 && dp[n][m] == dp[n - 1][m] + (pfa[n] + pfb[m]) * u[l[n - 1]]) {
                merged.emplace_back(l[n - 1]);
                n--;
            } else if (m > 0 && dp[n][m] == dp[n][m - 1] + (pfa[n] + pfb[m]) * u[r[m - 1]]) {
                merged.emplace_back(r[m - 1]);
                m--;
            } else
                assert(0);
        }

        reverse(all(merged));
        return merged;
    };

    // auto Merge = [&](vector<int> a, vector<int> b) {
    //     int sa = (int) a.size(), sb = (int) b.size();
    //     vector<long long> da(sa + 1), db(sb + 1);
    //     for (int i = 0; i < sa; i++) {
    //         da[i + 1] = da[i] + d[a[i]];
    //     }
    //     for (int i = 0; i < sb; i++) {
    //         db[i + 1] = db[i] + d[b[i]];
    //     }
    //     const long long inf = (long long) 1e18;
    //     vector<vector<long long>> dp(sa + 1, vector<long long>(sb + 1, inf));
    //     dp[0][0] = 0;
    //     for (int i = 0; i <= sa; i++) {
    //         for (int j = 0; j <= sb; j++) {
    //             if (i < sa) {
    //                 dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + (da[i + 1] + db[j]) * u[a[i]]);
    //             }
    //             if (j < sb) {
    //                 dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + (da[i] + db[j + 1]) * u[b[j]]);
    //             }
    //         }
    //     }
    //     vector<int> c;
    //     int x = sa, y = sb;
    //     while (x > 0 || y > 0) {
    //         if (x > 0 && dp[x][y] == dp[x - 1][y] + (da[x] + db[y]) * u[a[x - 1]]) {
    //             c.emplace_back(a[x - 1]);
    //             x--;
    //         } else if (y > 0 && dp[x][y] == dp[x][y - 1] + (da[x] + db[y]) * u[b[y - 1]]) {
    //             c.emplace_back(b[y - 1]);
    //             y--;
    //         } else {
    //             assert(false);
    //         }
    //     }
    //     reverse(c.begin(), c.end());
    //     return c;
    // };

    vector <vector <int>> job(sz(p));
    auto dfs = [&](auto &&self, int u) -> void {
        for (int v : adj[u]) {
            self(self, v);
            job[u] = Merge(job[u], job[v]);
        }

        job[u].insert(job[u].begin(), u);
    };

    dfs(dfs, 0);

    long long tot_time = 0, ans = 0;
    for (int id : job[0]) {
        tot_time += d[id];
        ans += tot_time * u[id];
    }

    return ans;
}

// void solve() {
//     cout << scheduling_cost({ -1, 0, 0 }, { 5, 2, 5 }, { 3, 4, 1 }) << '\n';
// }

// 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 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -