Submission #387756

#	Time	Username	Problem	Language	Result	Execution time	Memory
387756		rama_pang	Escape Route (JOI21_escape_route)	C++17	100 / 100	6099 ms	142384 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). This yields O(N^5 + Q N).
  //
  // To speed it up, for every vertex u, and edge adjacent to u, we calculate
  // the minimum time to reach all vertices v in the same day. Then, instead
  // of banning an edge, we add an edge instead by sweeping backwards.
  // Observet the condition when banning an edge: the minimum C[i] - L[i] - dist[i].
  // For all edges e adjacent to u, we sort them by C[e] - L[e]. Then, for every vertex,
  // we only need to consider a single edge (the largest C[e] - L[e]), and add them one
  // by one. This can be done via a priority queue or segment tree. Then, after getting
  // the maximum edge e, we reupdate all distances in O(N).
  //
  // Time complexity: O(N^4 log N + Q N).

  M = M + M;
  for (int i = 0; i < M / 2; i++) {
    A.push_back(B[i]);
    B.push_back(A[i]);
    L.push_back(L[i]);
    C.push_back(C[i]);
  }

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

  const auto Dijkstra = [&](int s, vector<lint> &dist, lint init) {
    dist.assign(N, inf);
    vector<int> done(N);
    dist[s] = init;
    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]) {
        int v = B[e];
        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]);
        }
      }
    }
  };

  // distance between cities (i, v) if we start at time 0.
  vector<vector<lint>> dist0(N, vector<lint>(N, inf));
  for (int s = 0; s < N; s++) {
    Dijkstra(s, dist0[s], 0);
  }

  // distance between cities (A[i], v) if we start at time C[e] - L[e]
  // must arrive at same day
  vector<vector<lint>> distE(M, vector<lint>(N));
  for (int e = 0; e < M; e++) {
    Dijkstra(A[e], distE[e], C[e] - L[e]);
    for (int i = 0; i < N; i++) {
      if (distE[e][i] < S) {
        distE[e][i] -= C[e] - L[e];
      } else {
        distE[e][i] = inf;
      }
    }
  }

  for (int u = 0; u < N; u++) {
    sort(begin(adj[u]), end(adj[u]), [&](int i, int j) {
      return C[i] - L[i] > C[j] - L[j];
    });
  }

  vector<vector<int>> queries(N);
  for (int q = 0; q < Q; q++) {
    queries[U[q]].emplace_back(q);
  }

  vector<lint> ans(Q, inf);
  for (int s = 0; s < N; s++) {
    auto &query = queries[s];
    sort(begin(query), end(query), [&](int i, int j) {
      return T[i] < T[j];
    });

    vector<int> ptr(N);
    vector<lint> dist(N, inf);
    dist[s] = 0;

    // Segment Tree
    vector<pair<lint, int>> tree(2 * N, {-1, -1});
    const auto Update = [&](int p, lint x) {
      const pair<lint, int> val = {x, p};
      tree[p += N] = val;
      for (p /= 2; p > 0; p /= 2) {
        tree[p] = max(tree[p * 2], tree[p * 2 + 1]);
      }
    };
    const auto Query = [&](int l, int r) {
      pair<lint, int> res = {-1, -1};
      for (l += N, r += N; l < r; l /= 2, r /= 2) {
        if (l & 1) res = max(res, tree[l++]);
        if (r & 1) res = max(res, tree[--r]);
      }
      return res;
    };

    Update(s, C[adj[s][ptr[s]]] - L[adj[s][ptr[s]]]);
    while (true) {
      auto top = Query(0, N);
      lint cur_time = top.first;
      while (!query.empty() && T[query.back()] > cur_time) {
        int q = query.back(); query.pop_back();
        for (int m = 0; m < N; m++) { // answer query, brute force when first day ends
          ans[q] = min(ans[q], dist[m] + (m != V[q]) * ((S - (dist[m] + T[q]) % S) % S) + dist0[m][V[q]]);
        }
      }

      if (cur_time < 0) break;

      int u = top.second;
      int e = adj[u][ptr[u]];

      ptr[u]++;
      if (ptr[u] < adj[u].size()) {
        Update(u, C[adj[u][ptr[u]]] - L[adj[u][ptr[u]]] - dist[u]);
      } else {
        Update(u, -1);
      }

      assert(u == A[e]);
      for (int v = 0; v < N; v++) if (distE[e][v] != inf) {
        if (dist[v] > dist[u] + distE[e][v]) {
          dist[v] = dist[u] + distE[e][v];
          if (ptr[v] < adj[v].size()) {
            Update(v, min(cur_time, C[adj[v][ptr[v]]] - L[adj[v][ptr[v]]] - dist[v]));
          }
        }
      }
    }
  }

  return ans;
}

Compilation message (stderr)

escape_route.cpp: In function 'std::vector<long long int> calculate_necessary_time(int, int, lint, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<long long int>, std::vector<int>, std::vector<int>, std::vector<long long int>)':
escape_route.cpp:167:18: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |       if (ptr[u] < adj[u].size()) {
escape_route.cpp:177:22: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |           if (ptr[v] < adj[v].size()) {

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