NOI 2020 - 美食家

Problem Link: LOJ3339

Solution

Sort the events by time.

Note that $w \leq 5$, which means that we can separate each edge into edges of weight $1$. Specifically, we can replace each node $i$ ($0$-indexed) with nodes $5i, 5i + 1, \dots, 5i + 4$ handling edges of weight $1 \dots 5$. Nodes $5i + j$ and $5i + (j + 1)$ for $0 \leq j < 4$ have an edge of weight $1$ and edges $u, v, w$ ($0$-indexed) are transformed into an edge $5u + (w - 1) \rightarrow 5v$ with weight $1$.

Now that all edge weights are $1$, we can use binary lifting to compute the answer. Let $jmp[i][u][v]$ represent the maximum total joy value if Xiao W travels for $2^i$ days from node $u$ to node $v$, besides the food festivals and initial node. We compute transitions as follows:

\[jmp[i][u][v] = \max_{0 \leq mid < 5n} (jmp[i - 1][u][mid] + jmp[i - 1][mid][v]).\]

Each transition takes $\mathcal{O}(n^3)$ time, so computing the binary jump takes $\mathcal{O}(n^3 \log T)$ time.

Now that we have the binary lift, we can compute $dp[t][v]$, which represents the maximum joy Xiao W can get by travelling for $t$ days and ending at node $v$, taking food festivals into consideration. We compute $dp$ for each food festival, as well as $t = 0$ and $t = T$. Let $joy[u][v]$ represent the maxiumum joy Xiao W gets when travelling from $u$ to $v$ in $t_i - t_{i - 1}$ days, computed using the same transitions above. Then, the transitions for $dp$ are

\[dp[t_i][u] = \max_{0 \leq v < 5n} (dp[t_{i - 1}][v] + joy[v][u]).\]

However, this leads to a time complexity of $\mathcal{O}(k n^3 \log T)$, because we have to compute $joy$, which takes $\mathcal{O}(n^3 \log T)$.

To make this faster, we can add new food festivals such that the difference between consecutive food festivals is a power of two, allowing us to use the previously-computed $jmp$ values without more computation. Using the same $dp$ transitions above, which takes $\mathcal{O}(n^2)$, we achieve a time complexity of $\mathcal{O}((n^3 + kn^2) \log T)$.

Implementation

/**
 * @author n685
 * @brief
 * @date 2024-07-31 11:59:57
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
void bar() {}
#endif

template <class T> constexpr T INF = T{};
template <std::floating_point T>
constexpr T INF<T> = std::numeric_limits<T>::infinity();
template <> constexpr int INF<int> = 0x3f3f3f3f; // 1061109567
template <>
constexpr int64_t INF<int64_t> = 0x3f3f3f3f3f3f3f3f; // 4557430888798830399

constexpr int LG = std::bit_width<uint32_t>(1'000'000'000); // 30
template <class T> T &chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
  }
  return a;
}

struct Event {
  int64_t t;
  int x;
  int64_t y;
};

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::freopen("delicacy.in", "r", stdin);
  std::freopen("delicacy.out", "w", stdout);
#endif

  int n, m;
  int64_t t;
  int k;
  std::cin >> n >> m >> t >> k;
  std::vector<int64_t> c(5 * n);
  for (int i = 0; i < n; ++i) {
    std::cin >> c[5 * i];
  }
  std::array<std::vector<std::vector<int64_t>>, LG> jmp;
  jmp.fill(std::vector(5 * n, std::vector(5 * n, -INF<int64_t>)));
  for (int i = 0; i < n; ++i) {
    for (int j = 1; j <= 4; ++j) {
      jmp[0][5 * i + (j - 1)][5 * i + j] = 0;
    }
  }
  n = 5 * n;
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    std::cin >> u >> v >> w;
    --u;
    --v;
    u = 5 * u;
    v = 5 * v;
    chmax(jmp[0][u + (w - 1)][v], c[v]);
  }
  std::vector<Event> pe;
  pe.emplace_back(0, -1, -1);
  int64_t evt = 0;
  for (int i = 0; i < k; ++i) {
    int64_t tt;
    int x;
    int64_t y;
    std::cin >> tt >> x >> y;
    x = 5 * (x - 1);
    if (tt != t) {
      pe.emplace_back(tt, x, y);
    } else {
      if (x == 0) {
        evt = y;
      }
    }
  }
  pe.emplace_back(t, 0, evt);
  std::ranges::sort(pe, {}, &Event::t);

  std::vector<Event> ev;
  ev.emplace_back(0, -1, -1);
  for (int i = 1; i < std::ssize(pe); ++i) {
    auto [tt, x, y] = pe[i];
    int64_t pt = ev.back().t;
    for (int j = LG - 1; j >= 0; --j) {
      if (tt - pt >= (int64_t{1} << j)) {
        ev.emplace_back(pt + (int64_t{1} << j), -1, -1);
        pt += int64_t{1} << j;
      }
    }
    ev.back().x = x;
    ev.back().y = y;
  }

  for (int l = 1; l < LG; ++l) {
    for (int mid = 0; mid < n; ++mid) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          chmax(jmp[l][i][j], jmp[l - 1][i][mid] + jmp[l - 1][mid][j]);
        }
      }
    }
  }
  std::vector pre(n, -INF<int64_t>);
  pre[0] = c[0];
  for (int i = 1; i < std::ssize(ev); ++i) {
    auto [tt, x, y] = ev[i];
    int lg = std::bit_width<uint64_t>(tt - ev[i - 1].t) - 1;
    std::vector cur(n, -INF<int64_t>);
    for (int ini = 0; ini < n; ++ini) {
      for (int dest = 0; dest < n; ++dest) {
        chmax(cur[dest], pre[ini] + jmp[lg][ini][dest]);
      }
    }
    if (x != -1) {
      cur[x] += y;
    }
    pre.swap(cur);
  }
  if (pre[0] <= -INF<int64_t> / 2) {
    std::cout << "-1\n";
  } else {
    std::cout << pre[0] << '\n';
  }
}