Submission #417398

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
417398	2021-06-03T16:17:40 Z	rama_pang	Job Scheduling (IOI19_job)	C++17	7 / 100	291 ms	73420 KB

#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 u * o.d > 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
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Runtime error	1 ms	460 KB	Execution killed with signal 6
4	Halted	0 ms	0 KB	-

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	289 ms	38612 KB	Output is correct
5	Correct	274 ms	38580 KB	Output is correct
6	Correct	276 ms	38592 KB	Output is correct
7	Correct	291 ms	38584 KB	Output is correct
8	Correct	269 ms	38576 KB	Output is correct
9	Correct	272 ms	38632 KB	Output is correct
10	Correct	268 ms	38656 KB	Output is correct
11	Correct	280 ms	38588 KB	Output is correct

Subtask #3
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Incorrect	7 ms	2196 KB	Output isn't correct
6	Halted	0 ms	0 KB	-