Submission #387610

#	Time	Username	Problem	Language	Result	Execution time	Memory
387610		rama_pang	Escape Route (JOI21_escape_route)	C++17	70 / 100	9023 ms	197148 KiB

escape_route

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

using lint = long long;
const lint inf = 1e18;

vector<lint> calculate_necessary_time(
    int N, int M, lint S, int Q,
    vector<int> A, vector<int> B,
    vector<lint> L, vector<lint> C,
    vector<int> U, vector<int> V, vector<lint> T) {

  // Solution:
  //
  // First, we compute the minimum time between any 2 cities
  // x and y, if we start from city x at time 0. We can
  // compute this in O(N^3) with Dijkstra.
  //
  // Next, process each starting city independently.
  // Generate the shortest path, assuming there is no restriction
  // on roads, and day is indefinitely long. Then, there is an
  // edge which is the "bottleneck" - the maximum time we can start
  // at source to generate this particular shortest path tree.
  // The bottleneck is the minimum C[i] - L[i] - dist[A[i]] if we
  // use the i-th edge in shortest path tree to go from A[i] to B[i].
  //
  // After identifying the bottleneck, if we start at any time before
  // the bottleneck, we can go to the other cities in time dist[v].
  // After arriving at city v, we will have to wait until the next day,
  // then start the journey again. However, we already computed the minimum
  // time to go from any 2 cities if we start at time 0. Thus, we can
  // process a single query by bruteforcing the city where we wait until
  // the next day.
  //
  // Since after deleting a bottleneck, we recompute the shortest path tree,
  // we need O(N^2) recomputations in O(N^2) time each. There are O(N) sources,
  // and each query is done in O(N).
  //
  // Time complexity: O(N^5 + Q N + Q log Q).

  // adjacency list
  vector<vector<int>> adj(N);
  for (int i = 0; i < M; i++) {
    adj[A[i]].push_back(i);
    adj[B[i]].push_back(i);
  }

  // distance between 2 cities if we start at time 0.
  vector<vector<lint>> dist0(N, vector<lint>(N, inf));
  for (int s = 0; s < N; s++) {
    auto &dist = dist0[s];
    vector<int> done(N);
    dist[s] = 0;
    for (int rep = 0; rep < N; rep++) {
      int u = -1;
      for (int v = 0; v < N; v++) if (!done[v]) {
        if (u == -1 || dist[u] > dist[v]) {
          u = v;
        }
      }
      done[u] = 1;
      for (auto e : adj[u]) {
        int v = A[e] ^ B[e] ^ u;
        if ((dist[u] % S) <= C[e] - L[e]) {
          dist[v] = min(dist[v], dist[u] + L[e]);
        } else {
          dist[v] = min(dist[v], dist[u] + (S - dist[u] % S) % S + L[e]);
        }
      }
    }
  }

  vector<lint> ans(Q, inf);
  for (int s = 0; s < N; s++) {
    vector<int> banned(M);
    vector<vector<pair<lint, lint>>> ls(N); // list of (bottleneck, distance)

    vector<int> used(M);
    vector<lint> dist(N);

    const auto Dijkstra = [&]() {
      fill(begin(used), end(used), 0);
      fill(begin(dist), end(dist), inf);
      vector<int> prv(N, -1);
      vector<int> done(N);
      dist[s] = 0;
      for (int rep = 0; rep < N; rep++) {
        int u = -1;
        for (int v = 0; v < N; v++) if (!done[v]) {
          if (u == -1 || dist[u] > dist[v]) {
            u = v;
          }
        }
        if (dist[u] == inf) break;
        done[u] = 1;
        for (auto e : adj[u]) if (!banned[e]) {
          int v = A[e] ^ B[e] ^ u;
          if (dist[u] <= C[e] - L[e] && dist[v] > dist[u] + L[e]) {
            if (prv[v] != -1) used[prv[v]] = 0;
            dist[v] = dist[u] + L[e];
            used[e] = 1;
            prv[v] = e;
          }
        }
      }
    };

    for (int rep = 0; rep < M + 1; rep++) {
      Dijkstra();
      pair<lint, int> bottleneck = {inf, -1};
      for (int e = 0; e < M; e++) if (used[e]) {
        if (dist[A[e]] < dist[B[e]]) {
          bottleneck = min(bottleneck, {C[e] - dist[B[e]], e});
        } else {
          bottleneck = min(bottleneck, {C[e] - dist[A[e]], e});
        }
      }
      if (bottleneck.second == -1) break;
      banned[bottleneck.second] = 1;
      for (int u = 0; u < N; u++) if (dist[u] != inf) {
        if (ls[u].empty() || ls[u].back().first < bottleneck.first) {
          assert(ls[u].empty() || ls[u].back().second <= dist[u]);
          ls[u].emplace_back(bottleneck.first, dist[u]);
        }
      }
    }

    ls[s].emplace_back(inf, 0);
    for (int u = 0; u < N; u++) {
      for (int i = 0; i + 1 < (int) ls[u].size(); i++) {
        assert(ls[u][i].first <= ls[u][i + 1].first);
        assert(ls[u][i].second <= ls[u][i + 1].second);
      }
      reverse(begin(ls[u]), end(ls[u]));
    }

    vector<int> query;
    for (int q = 0; q < Q; q++) if (U[q] == s) {
      query.emplace_back(q);
    }
    sort(begin(query), end(query), [&](int i, int j) { return T[i] < T[j]; });
    for (auto q : query) {
      for (int m = 0; m < N; m++) {
        while (!ls[m].empty() && T[q] > ls[m].back().first) {
          ls[m].pop_back();
        }
        lint dt = ls[m].empty() ? inf : ls[m].back().second;
        ans[q] = min(ans[q], dt + (m != V[q]) * ((S - (dt + T[q]) % S) % S) + dist0[m][V[q]]);
      }
    }
  }

  return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35
• Subtask 5: 0 / 30