oj.uz

Submission #388803

# Submission time Handle Problem Language Result Execution time Memory
388803 2021-04-13T04:26:34 Z rama_pang Escape Route (JOI21_escape_route) C++17
100 / 100
 5654 ms 195056 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).
  //
  // However, there are only O(N^2) total "pops" for every source, so we can use
  // an array instead to update distance in O(1) and query maximum in O(N).
  //
  // Time complexity: O(N^4 + 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;

    vector<lint> elems(N, -1);
    vector<pair<lint, int>> tree(2 * N, {-1, -1});
    const auto Update = [&](int p, lint x) {
      elems[p] = x;
    };
    const auto GetMax = [&]() {
      pair<lint, int> res = {-1, -1};
      for (int i = 0; i < N; i++) {
        res = max(res, {elems[i], i});
      }
      return res;
    };

    Update(s, C[adj[s][ptr[s]]] - L[adj[s][ptr[s]]]);
    while (true) {
      auto top = GetMax();
      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:165: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]
  165 |       if (ptr[u] < adj[u].size()) {
escape_route.cpp:175: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]
  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 34 ms 64924 KB Output is correct
3 Correct 79 ms 65056 KB Output is correct
4 Correct 29 ms 64972 KB Output is correct
5 Correct 60 ms 65056 KB Output is correct
6 Correct 29 ms 64972 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2747 ms 154744 KB Output is correct
2 Correct 2848 ms 154360 KB Output is correct
3 Correct 3004 ms 153992 KB Output is correct
4 Correct 4006 ms 160880 KB Output is correct
5 Correct 2830 ms 160800 KB Output is correct
6 Correct 30 ms 64924 KB Output is correct
7 Correct 2965 ms 155044 KB Output is correct
8 Correct 3046 ms 172888 KB Output is correct
9 Correct 2830 ms 154964 KB Output is correct
10 Correct 2852 ms 160500 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 34 ms 64924 KB Output is correct
3 Correct 79 ms 65056 KB Output is correct
4 Correct 29 ms 64972 KB Output is correct
5 Correct 60 ms 65056 KB Output is correct
6 Correct 29 ms 64972 KB Output is correct
7 Correct 2747 ms 154744 KB Output is correct
8 Correct 2848 ms 154360 KB Output is correct
9 Correct 3004 ms 153992 KB Output is correct
10 Correct 4006 ms 160880 KB Output is correct
11 Correct 2830 ms 160800 KB Output is correct
12 Correct 30 ms 64924 KB Output is correct
13 Correct 2965 ms 155044 KB Output is correct
14 Correct 3046 ms 172888 KB Output is correct
15 Correct 2830 ms 154964 KB Output is correct
16 Correct 2852 ms 160500 KB Output is correct
17 Correct 2579 ms 156324 KB Output is correct
18 Correct 2610 ms 156580 KB Output is correct
19 Correct 2646 ms 156428 KB Output is correct
20 Correct 2715 ms 156332 KB Output is correct
21 Correct 2652 ms 162636 KB Output is correct
22 Correct 2654 ms 162124 KB Output is correct
23 Correct 2645 ms 155928 KB Output is correct
24 Correct 2823 ms 173940 KB Output is correct
25 Correct 2579 ms 156104 KB Output is correct
26 Correct 2696 ms 162080 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 34 ms 64924 KB Output is correct
3 Correct 79 ms 65056 KB Output is correct
4 Correct 29 ms 64972 KB Output is correct
5 Correct 60 ms 65056 KB Output is correct
6 Correct 29 ms 64972 KB Output is correct
7 Correct 2747 ms 154744 KB Output is correct
8 Correct 2848 ms 154360 KB Output is correct
9 Correct 3004 ms 153992 KB Output is correct
10 Correct 4006 ms 160880 KB Output is correct
11 Correct 2830 ms 160800 KB Output is correct
12 Correct 30 ms 64924 KB Output is correct
13 Correct 2965 ms 155044 KB Output is correct
14 Correct 3046 ms 172888 KB Output is correct
15 Correct 2830 ms 154964 KB Output is correct
16 Correct 2852 ms 160500 KB Output is correct
17 Correct 2579 ms 156324 KB Output is correct
18 Correct 2610 ms 156580 KB Output is correct
19 Correct 2646 ms 156428 KB Output is correct
20 Correct 2715 ms 156332 KB Output is correct
21 Correct 2652 ms 162636 KB Output is correct
22 Correct 2654 ms 162124 KB Output is correct
23 Correct 2645 ms 155928 KB Output is correct
24 Correct 2823 ms 173940 KB Output is correct
25 Correct 2579 ms 156104 KB Output is correct
26 Correct 2696 ms 162080 KB Output is correct
27 Correct 3399 ms 152664 KB Output is correct
28 Correct 3924 ms 152496 KB Output is correct
29 Correct 3462 ms 157012 KB Output is correct
30 Correct 3607 ms 157116 KB Output is correct
31 Correct 3525 ms 163140 KB Output is correct
32 Correct 3502 ms 162212 KB Output is correct
33 Correct 3500 ms 173172 KB Output is correct
34 Correct 3397 ms 150844 KB Output is correct
35 Correct 3517 ms 162212 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 34 ms 64924 KB Output is correct
3 Correct 79 ms 65056 KB Output is correct
4 Correct 29 ms 64972 KB Output is correct
5 Correct 60 ms 65056 KB Output is correct
6 Correct 29 ms 64972 KB Output is correct
7 Correct 2747 ms 154744 KB Output is correct
8 Correct 2848 ms 154360 KB Output is correct
9 Correct 3004 ms 153992 KB Output is correct
10 Correct 4006 ms 160880 KB Output is correct
11 Correct 2830 ms 160800 KB Output is correct
12 Correct 30 ms 64924 KB Output is correct
13 Correct 2965 ms 155044 KB Output is correct
14 Correct 3046 ms 172888 KB Output is correct
15 Correct 2830 ms 154964 KB Output is correct
16 Correct 2852 ms 160500 KB Output is correct
17 Correct 2579 ms 156324 KB Output is correct
18 Correct 2610 ms 156580 KB Output is correct
19 Correct 2646 ms 156428 KB Output is correct
20 Correct 2715 ms 156332 KB Output is correct
21 Correct 2652 ms 162636 KB Output is correct
22 Correct 2654 ms 162124 KB Output is correct
23 Correct 2645 ms 155928 KB Output is correct
24 Correct 2823 ms 173940 KB Output is correct
25 Correct 2579 ms 156104 KB Output is correct
26 Correct 2696 ms 162080 KB Output is correct
27 Correct 3399 ms 152664 KB Output is correct
28 Correct 3924 ms 152496 KB Output is correct
29 Correct 3462 ms 157012 KB Output is correct
30 Correct 3607 ms 157116 KB Output is correct
31 Correct 3525 ms 163140 KB Output is correct
32 Correct 3502 ms 162212 KB Output is correct
33 Correct 3500 ms 173172 KB Output is correct
34 Correct 3397 ms 150844 KB Output is correct
35 Correct 3517 ms 162212 KB Output is correct
36 Correct 5446 ms 150440 KB Output is correct
37 Correct 5471 ms 158020 KB Output is correct
38 Correct 5533 ms 162232 KB Output is correct
39 Correct 5654 ms 188672 KB Output is correct
40 Correct 5613 ms 187740 KB Output is correct
41 Correct 4663 ms 195056 KB Output is correct
42 Correct 5534 ms 156328 KB Output is correct
43 Correct 5476 ms 156644 KB Output is correct