Submission #417399

#	Time	Username	Problem	Language	Result	Execution time	Memory
417399		rama_pang	Job Scheduling (IOI19_job)	C++17	100 / 100	399 ms	74208 KiB

job

#include "job.h"

#include <bits/stdc++.h>
using namespace std;

using lint = long long;

lint scheduling_cost(vector<int> P, vector<int> U, vector<int> D) {
  // Solution:
  // Assume there is no p[]. Let's ignore u[i] * d[i].
  //
  // Let's observe i and j. If i < j is optimal:
  // u[j] * d[i] < u[i] * d[j]
  // u[j] / d[j] < u[i] / d[i]
  // So, we sort by u[x] / d[x] in decreasing opt.
  // With this, we can solve for a star graph.
  //
  // Now, assume it's a tree, and we only have 2 children.
  // If the optimal ordering of the children is sorted
  // decreasingly by U[i] / D[i], then we can merge the
  // sorted list together.
  //
  // Assume we have a list = {U[i] / D[i], U[j] / D[j]} and {U[k] / D[k]}.
  // Also, U[i] / D[i] < U[j] / D[j].
  //
  // Since j comes after i, let's ignore U[j] * D[i].
  //
  // Cost if {i, j, k}:
  // U[k] * D[i] + U[k] * D[j]
  //
  // Cost if {k, i, j}:
  // U[i] * D[k] + U[j] * D[k]
  //
  // Cost if {i, k, j}:
  // U[k] * D[i] + U[j] * D[k]
  //
  // If {i, k, j} is optimal:
  // U[k] * D[i] + U[j] * D[k] < U[k] * D[i] + U[k] * D[j]
  // -> U[j] * D[k] < U[k] * D[j] -> U[j] / D[j] < U[k] / D[k]
  // U[k] * D[i] + U[j] * D[k] < U[i] * D[k] + U[j] * D[k]
  // -> U[k] * D[i] < U[i] * D[k] -> U[k] / D[k] < U[i] / D[i]
  // But U[i] / D[i] < U[j] / D[j], so contradiction.
  //
  // So only {i, j, k} or {k, i, j} can be optimal.
  // Thus, we can merge {i, j} together, so we always have a sorted
  // decreasingly list.
  //
  // With small to large, we have O(N log^2 N).

  int N = P.size();
  vector<vector<int>> adj(N);
  for (int i = 1; i < N; i++) {
    adj[P[i]].emplace_back(i);
  }

  struct Item {
    int u, d;
    Item(int u, int d) : u(u), d(d) {}
    const bool operator<(const Item &o) const {
      return 1ll * u * o.d > 1ll * o.u * d;
    }
  };

  lint ans = 0;
  for (int i = 0; i < N; i++) {
    ans += 1ll * U[i] * D[i];
  }

  vector<multiset<Item>> dp(N);
  const auto Dfs = [&](const auto &self, int u) -> void {
    for (auto v : adj[u]) {
      self(self, v);
      if (dp[u].size() < dp[v].size()) {
        swap(dp[u], dp[v]);
      }
      for (auto i : dp[v]) {
        dp[u].emplace(i);
      }
    }
    Item cur(U[u], D[u]);
    while (!dp[u].empty() && *begin(dp[u]) < cur) {
      auto it = *begin(dp[u]);
      dp[u].erase(dp[u].find(it));
      ans += 1ll * it.u * cur.d;
      cur.u += it.u;
      cur.d += it.d;
    }
    dp[u].emplace(cur);
  };

  int t = 0;
  Dfs(Dfs, 0);
  for (auto i : dp[0]) {
    ans += 1ll * t * i.u;
    t += i.d;
  }

  return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 37 / 37