oj.uz

Submission #387756

# Submission time Handle Problem Language Result Execution time Memory
387756 2021-04-09T07:26:19 Z rama_pang Escape Route (JOI21_escape_route) C++17
100 / 100
 6099 ms 142384 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) {
      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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 64972 KB Output is correct
2 Correct 37 ms 64948 KB Output is correct
3 Correct 78 ms 64960 KB Output is correct
4 Correct 32 ms 64976 KB Output is correct
5 Correct 63 ms 64964 KB Output is correct
6 Correct 31 ms 64928 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2875 ms 117108 KB Output is correct
2 Correct 2974 ms 126392 KB Output is correct
3 Correct 3022 ms 117916 KB Output is correct
4 Correct 3014 ms 130004 KB Output is correct
5 Correct 2992 ms 130180 KB Output is correct
6 Correct 31 ms 65016 KB Output is correct
7 Correct 2905 ms 117388 KB Output is correct
8 Correct 3124 ms 142072 KB Output is correct
9 Correct 2893 ms 117444 KB Output is correct
10 Correct 2989 ms 129716 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 64972 KB Output is correct
2 Correct 37 ms 64948 KB Output is correct
3 Correct 78 ms 64960 KB Output is correct
4 Correct 32 ms 64976 KB Output is correct
5 Correct 63 ms 64964 KB Output is correct
6 Correct 31 ms 64928 KB Output is correct
7 Correct 2875 ms 117108 KB Output is correct
8 Correct 2974 ms 126392 KB Output is correct
9 Correct 3022 ms 117916 KB Output is correct
10 Correct 3014 ms 130004 KB Output is correct
11 Correct 2992 ms 130180 KB Output is correct
12 Correct 31 ms 65016 KB Output is correct
13 Correct 2905 ms 117388 KB Output is correct
14 Correct 3124 ms 142072 KB Output is correct
15 Correct 2893 ms 117444 KB Output is correct
16 Correct 2989 ms 129716 KB Output is correct
17 Correct 2716 ms 117472 KB Output is correct
18 Correct 2668 ms 117444 KB Output is correct
19 Correct 2734 ms 127648 KB Output is correct
20 Correct 2818 ms 117500 KB Output is correct
21 Correct 2791 ms 130896 KB Output is correct
22 Correct 2767 ms 130300 KB Output is correct
23 Correct 2741 ms 117444 KB Output is correct
24 Correct 2905 ms 142120 KB Output is correct
25 Correct 2696 ms 117444 KB Output is correct
26 Correct 2786 ms 130356 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 64972 KB Output is correct
2 Correct 37 ms 64948 KB Output is correct
3 Correct 78 ms 64960 KB Output is correct
4 Correct 32 ms 64976 KB Output is correct
5 Correct 63 ms 64964 KB Output is correct
6 Correct 31 ms 64928 KB Output is correct
7 Correct 2875 ms 117108 KB Output is correct
8 Correct 2974 ms 126392 KB Output is correct
9 Correct 3022 ms 117916 KB Output is correct
10 Correct 3014 ms 130004 KB Output is correct
11 Correct 2992 ms 130180 KB Output is correct
12 Correct 31 ms 65016 KB Output is correct
13 Correct 2905 ms 117388 KB Output is correct
14 Correct 3124 ms 142072 KB Output is correct
15 Correct 2893 ms 117444 KB Output is correct
16 Correct 2989 ms 129716 KB Output is correct
17 Correct 2716 ms 117472 KB Output is correct
18 Correct 2668 ms 117444 KB Output is correct
19 Correct 2734 ms 127648 KB Output is correct
20 Correct 2818 ms 117500 KB Output is correct
21 Correct 2791 ms 130896 KB Output is correct
22 Correct 2767 ms 130300 KB Output is correct
23 Correct 2741 ms 117444 KB Output is correct
24 Correct 2905 ms 142120 KB Output is correct
25 Correct 2696 ms 117444 KB Output is correct
26 Correct 2786 ms 130356 KB Output is correct
27 Correct 3472 ms 117552 KB Output is correct
28 Correct 3546 ms 117432 KB Output is correct
29 Correct 3594 ms 128184 KB Output is correct
30 Correct 3681 ms 118072 KB Output is correct
31 Correct 3689 ms 131228 KB Output is correct
32 Correct 3668 ms 131128 KB Output is correct
33 Correct 3585 ms 142384 KB Output is correct
34 Correct 3517 ms 117444 KB Output is correct
35 Correct 3724 ms 131520 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 64972 KB Output is correct
2 Correct 37 ms 64948 KB Output is correct
3 Correct 78 ms 64960 KB Output is correct
4 Correct 32 ms 64976 KB Output is correct
5 Correct 63 ms 64964 KB Output is correct
6 Correct 31 ms 64928 KB Output is correct
7 Correct 2875 ms 117108 KB Output is correct
8 Correct 2974 ms 126392 KB Output is correct
9 Correct 3022 ms 117916 KB Output is correct
10 Correct 3014 ms 130004 KB Output is correct
11 Correct 2992 ms 130180 KB Output is correct
12 Correct 31 ms 65016 KB Output is correct
13 Correct 2905 ms 117388 KB Output is correct
14 Correct 3124 ms 142072 KB Output is correct
15 Correct 2893 ms 117444 KB Output is correct
16 Correct 2989 ms 129716 KB Output is correct
17 Correct 2716 ms 117472 KB Output is correct
18 Correct 2668 ms 117444 KB Output is correct
19 Correct 2734 ms 127648 KB Output is correct
20 Correct 2818 ms 117500 KB Output is correct
21 Correct 2791 ms 130896 KB Output is correct
22 Correct 2767 ms 130300 KB Output is correct
23 Correct 2741 ms 117444 KB Output is correct
24 Correct 2905 ms 142120 KB Output is correct
25 Correct 2696 ms 117444 KB Output is correct
26 Correct 2786 ms 130356 KB Output is correct
27 Correct 3472 ms 117552 KB Output is correct
28 Correct 3546 ms 117432 KB Output is correct
29 Correct 3594 ms 128184 KB Output is correct
30 Correct 3681 ms 118072 KB Output is correct
31 Correct 3689 ms 131228 KB Output is correct
32 Correct 3668 ms 131128 KB Output is correct
33 Correct 3585 ms 142384 KB Output is correct
34 Correct 3517 ms 117444 KB Output is correct
35 Correct 3724 ms 131520 KB Output is correct
36 Correct 5818 ms 118272 KB Output is correct
37 Correct 5934 ms 112072 KB Output is correct
38 Correct 5755 ms 116284 KB Output is correct
39 Correct 6086 ms 126640 KB Output is correct
40 Correct 6099 ms 126896 KB Output is correct
41 Correct 4640 ms 134160 KB Output is correct
42 Correct 5813 ms 112068 KB Output is correct
43 Correct 5901 ms 112032 KB Output is correct