oj.uz

Submission #387610

# Submission time Handle Problem Language Result Execution time Memory
387610 2021-04-09T03:55:42 Z rama_pang Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 197148 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).
  //
  // 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 65072 KB Output is correct
2 Correct 40 ms 65028 KB Output is correct
3 Correct 370 ms 65112 KB Output is correct
4 Correct 28 ms 64972 KB Output is correct
5 Correct 38 ms 64956 KB Output is correct
6 Correct 29 ms 65064 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3662 ms 154948 KB Output is correct
2 Correct 3736 ms 173220 KB Output is correct
3 Correct 3643 ms 153656 KB Output is correct
4 Correct 3755 ms 182692 KB Output is correct
5 Correct 3765 ms 182588 KB Output is correct
6 Correct 28 ms 64896 KB Output is correct
7 Correct 3648 ms 154936 KB Output is correct
8 Correct 3503 ms 194568 KB Output is correct
9 Correct 3752 ms 155056 KB Output is correct
10 Correct 3764 ms 182344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 65072 KB Output is correct
2 Correct 40 ms 65028 KB Output is correct
3 Correct 370 ms 65112 KB Output is correct
4 Correct 28 ms 64972 KB Output is correct
5 Correct 38 ms 64956 KB Output is correct
6 Correct 29 ms 65064 KB Output is correct
7 Correct 3662 ms 154948 KB Output is correct
8 Correct 3736 ms 173220 KB Output is correct
9 Correct 3643 ms 153656 KB Output is correct
10 Correct 3755 ms 182692 KB Output is correct
11 Correct 3765 ms 182588 KB Output is correct
12 Correct 28 ms 64896 KB Output is correct
13 Correct 3648 ms 154936 KB Output is correct
14 Correct 3503 ms 194568 KB Output is correct
15 Correct 3752 ms 155056 KB Output is correct
16 Correct 3764 ms 182344 KB Output is correct
17 Correct 3515 ms 157068 KB Output is correct
18 Correct 3496 ms 156996 KB Output is correct
19 Correct 3599 ms 176000 KB Output is correct
20 Correct 3495 ms 156488 KB Output is correct
21 Correct 3620 ms 185312 KB Output is correct
22 Correct 3662 ms 185096 KB Output is correct
23 Correct 3493 ms 157212 KB Output is correct
24 Correct 3403 ms 196528 KB Output is correct
25 Correct 3575 ms 157120 KB Output is correct
26 Correct 3635 ms 185276 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 65072 KB Output is correct
2 Correct 40 ms 65028 KB Output is correct
3 Correct 370 ms 65112 KB Output is correct
4 Correct 28 ms 64972 KB Output is correct
5 Correct 38 ms 64956 KB Output is correct
6 Correct 29 ms 65064 KB Output is correct
7 Correct 3662 ms 154948 KB Output is correct
8 Correct 3736 ms 173220 KB Output is correct
9 Correct 3643 ms 153656 KB Output is correct
10 Correct 3755 ms 182692 KB Output is correct
11 Correct 3765 ms 182588 KB Output is correct
12 Correct 28 ms 64896 KB Output is correct
13 Correct 3648 ms 154936 KB Output is correct
14 Correct 3503 ms 194568 KB Output is correct
15 Correct 3752 ms 155056 KB Output is correct
16 Correct 3764 ms 182344 KB Output is correct
17 Correct 3515 ms 157068 KB Output is correct
18 Correct 3496 ms 156996 KB Output is correct
19 Correct 3599 ms 176000 KB Output is correct
20 Correct 3495 ms 156488 KB Output is correct
21 Correct 3620 ms 185312 KB Output is correct
22 Correct 3662 ms 185096 KB Output is correct
23 Correct 3493 ms 157212 KB Output is correct
24 Correct 3403 ms 196528 KB Output is correct
25 Correct 3575 ms 157120 KB Output is correct
26 Correct 3635 ms 185276 KB Output is correct
27 Correct 7313 ms 157652 KB Output is correct
28 Correct 7427 ms 157636 KB Output is correct
29 Correct 7707 ms 174792 KB Output is correct
30 Correct 6602 ms 157020 KB Output is correct
31 Correct 7892 ms 184392 KB Output is correct
32 Correct 7595 ms 184700 KB Output is correct
33 Correct 4151 ms 197148 KB Output is correct
34 Correct 7187 ms 157764 KB Output is correct
35 Correct 7533 ms 185180 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 65072 KB Output is correct
2 Correct 40 ms 65028 KB Output is correct
3 Correct 370 ms 65112 KB Output is correct
4 Correct 28 ms 64972 KB Output is correct
5 Correct 38 ms 64956 KB Output is correct
6 Correct 29 ms 65064 KB Output is correct
7 Correct 3662 ms 154948 KB Output is correct
8 Correct 3736 ms 173220 KB Output is correct
9 Correct 3643 ms 153656 KB Output is correct
10 Correct 3755 ms 182692 KB Output is correct
11 Correct 3765 ms 182588 KB Output is correct
12 Correct 28 ms 64896 KB Output is correct
13 Correct 3648 ms 154936 KB Output is correct
14 Correct 3503 ms 194568 KB Output is correct
15 Correct 3752 ms 155056 KB Output is correct
16 Correct 3764 ms 182344 KB Output is correct
17 Correct 3515 ms 157068 KB Output is correct
18 Correct 3496 ms 156996 KB Output is correct
19 Correct 3599 ms 176000 KB Output is correct
20 Correct 3495 ms 156488 KB Output is correct
21 Correct 3620 ms 185312 KB Output is correct
22 Correct 3662 ms 185096 KB Output is correct
23 Correct 3493 ms 157212 KB Output is correct
24 Correct 3403 ms 196528 KB Output is correct
25 Correct 3575 ms 157120 KB Output is correct
26 Correct 3635 ms 185276 KB Output is correct
27 Correct 7313 ms 157652 KB Output is correct
28 Correct 7427 ms 157636 KB Output is correct
29 Correct 7707 ms 174792 KB Output is correct
30 Correct 6602 ms 157020 KB Output is correct
31 Correct 7892 ms 184392 KB Output is correct
32 Correct 7595 ms 184700 KB Output is correct
33 Correct 4151 ms 197148 KB Output is correct
34 Correct 7187 ms 157764 KB Output is correct
35 Correct 7533 ms 185180 KB Output is correct
36 Execution timed out 9023 ms 158076 KB Time limit exceeded
37 Halted 0 ms 0 KB -