oj.uz

Submission #387750

# Submission time Handle Problem Language Result Execution time Memory
387750 2021-04-09T07:17:35 Z rama_pang Escape Route (JOI21_escape_route) C++17
100 / 100
 8074 ms 197792 KB 
#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) {
      tree[p + N] = {x, p}; p += N;
      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) {
        dist[v] = min(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

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:166: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]
  166 |       if (ptr[u] < adj[u].size()) {
escape_route.cpp:175:20: 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]
  175 |         if (ptr[v] < adj[v].size()) {

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64972 KB Output is correct
2 Correct 36 ms 64972 KB Output is correct
3 Correct 133 ms 65100 KB Output is correct
4 Correct 29 ms 64972 KB Output is correct
5 Correct 61 ms 65072 KB Output is correct
6 Correct 30 ms 64972 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2927 ms 114060 KB Output is correct
2 Correct 3000 ms 123644 KB Output is correct
3 Correct 3044 ms 114396 KB Output is correct
4 Correct 3007 ms 124848 KB Output is correct
5 Correct 3002 ms 124796 KB Output is correct
6 Correct 28 ms 64972 KB Output is correct
7 Correct 3034 ms 113988 KB Output is correct
8 Correct 3119 ms 136824 KB Output is correct
9 Correct 3008 ms 114036 KB Output is correct
10 Correct 3000 ms 124360 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64972 KB Output is correct
2 Correct 36 ms 64972 KB Output is correct
3 Correct 133 ms 65100 KB Output is correct
4 Correct 29 ms 64972 KB Output is correct
5 Correct 61 ms 65072 KB Output is correct
6 Correct 30 ms 64972 KB Output is correct
7 Correct 2927 ms 114060 KB Output is correct
8 Correct 3000 ms 123644 KB Output is correct
9 Correct 3044 ms 114396 KB Output is correct
10 Correct 3007 ms 124848 KB Output is correct
11 Correct 3002 ms 124796 KB Output is correct
12 Correct 28 ms 64972 KB Output is correct
13 Correct 3034 ms 113988 KB Output is correct
14 Correct 3119 ms 136824 KB Output is correct
15 Correct 3008 ms 114036 KB Output is correct
16 Correct 3000 ms 124360 KB Output is correct
17 Correct 2758 ms 113944 KB Output is correct
18 Correct 2747 ms 113948 KB Output is correct
19 Correct 2784 ms 124496 KB Output is correct
20 Correct 2821 ms 113860 KB Output is correct
21 Correct 2802 ms 125624 KB Output is correct
22 Correct 2828 ms 125088 KB Output is correct
23 Correct 2794 ms 113928 KB Output is correct
24 Correct 2912 ms 136764 KB Output is correct
25 Correct 2733 ms 113860 KB Output is correct
26 Correct 2827 ms 125116 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64972 KB Output is correct
2 Correct 36 ms 64972 KB Output is correct
3 Correct 133 ms 65100 KB Output is correct
4 Correct 29 ms 64972 KB Output is correct
5 Correct 61 ms 65072 KB Output is correct
6 Correct 30 ms 64972 KB Output is correct
7 Correct 2927 ms 114060 KB Output is correct
8 Correct 3000 ms 123644 KB Output is correct
9 Correct 3044 ms 114396 KB Output is correct
10 Correct 3007 ms 124848 KB Output is correct
11 Correct 3002 ms 124796 KB Output is correct
12 Correct 28 ms 64972 KB Output is correct
13 Correct 3034 ms 113988 KB Output is correct
14 Correct 3119 ms 136824 KB Output is correct
15 Correct 3008 ms 114036 KB Output is correct
16 Correct 3000 ms 124360 KB Output is correct
17 Correct 2758 ms 113944 KB Output is correct
18 Correct 2747 ms 113948 KB Output is correct
19 Correct 2784 ms 124496 KB Output is correct
20 Correct 2821 ms 113860 KB Output is correct
21 Correct 2802 ms 125624 KB Output is correct
22 Correct 2828 ms 125088 KB Output is correct
23 Correct 2794 ms 113928 KB Output is correct
24 Correct 2912 ms 136764 KB Output is correct
25 Correct 2733 ms 113860 KB Output is correct
26 Correct 2827 ms 125116 KB Output is correct
27 Correct 3818 ms 113860 KB Output is correct
28 Correct 3833 ms 113860 KB Output is correct
29 Correct 3884 ms 124936 KB Output is correct
30 Correct 3985 ms 114404 KB Output is correct
31 Correct 4152 ms 125740 KB Output is correct
32 Correct 4293 ms 125976 KB Output is correct
33 Correct 3637 ms 136956 KB Output is correct
34 Correct 3896 ms 113860 KB Output is correct
35 Correct 4032 ms 126232 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64972 KB Output is correct
2 Correct 36 ms 64972 KB Output is correct
3 Correct 133 ms 65100 KB Output is correct
4 Correct 29 ms 64972 KB Output is correct
5 Correct 61 ms 65072 KB Output is correct
6 Correct 30 ms 64972 KB Output is correct
7 Correct 2927 ms 114060 KB Output is correct
8 Correct 3000 ms 123644 KB Output is correct
9 Correct 3044 ms 114396 KB Output is correct
10 Correct 3007 ms 124848 KB Output is correct
11 Correct 3002 ms 124796 KB Output is correct
12 Correct 28 ms 64972 KB Output is correct
13 Correct 3034 ms 113988 KB Output is correct
14 Correct 3119 ms 136824 KB Output is correct
15 Correct 3008 ms 114036 KB Output is correct
16 Correct 3000 ms 124360 KB Output is correct
17 Correct 2758 ms 113944 KB Output is correct
18 Correct 2747 ms 113948 KB Output is correct
19 Correct 2784 ms 124496 KB Output is correct
20 Correct 2821 ms 113860 KB Output is correct
21 Correct 2802 ms 125624 KB Output is correct
22 Correct 2828 ms 125088 KB Output is correct
23 Correct 2794 ms 113928 KB Output is correct
24 Correct 2912 ms 136764 KB Output is correct
25 Correct 2733 ms 113860 KB Output is correct
26 Correct 2827 ms 125116 KB Output is correct
27 Correct 3818 ms 113860 KB Output is correct
28 Correct 3833 ms 113860 KB Output is correct
29 Correct 3884 ms 124936 KB Output is correct
30 Correct 3985 ms 114404 KB Output is correct
31 Correct 4152 ms 125740 KB Output is correct
32 Correct 4293 ms 125976 KB Output is correct
33 Correct 3637 ms 136956 KB Output is correct
34 Correct 3896 ms 113860 KB Output is correct
35 Correct 4032 ms 126232 KB Output is correct
36 Correct 7823 ms 114680 KB Output is correct
37 Correct 7907 ms 158020 KB Output is correct
38 Correct 8074 ms 162236 KB Output is correct
39 Correct 7893 ms 190296 KB Output is correct
40 Correct 7921 ms 190720 KB Output is correct
41 Correct 4838 ms 197792 KB Output is correct
42 Correct 7849 ms 158148 KB Output is correct
43 Correct 7762 ms 158088 KB Output is correct