Escape Route - 70p

#pragma GCC optimize("unroll-loops")
#include "escape_route.h"
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

namespace {

struct Edge {
  int to;
  int64_t cost, bad_time;
};

const int N = 90;
const int64_t INF_LL = (int64_t)8e18 + 10;

int n;
vector<Edge> adj[N];
int64_t ans[N];
bool vis[N];

void GetConstraints(int start_node, int64_t start_time) {
  for (int i = 0; i < n; ++i) {
    vis[i] = false;
    ans[i] = -1;
  }
  ans[start_node] = start_time;

  while (true) {
    pair<int64_t, int> best = {-1, -1};
    for (int node = 0; node < n; ++node) {
      if (vis[node] || ans[node] == -1) continue;
      best = max(best, {ans[node], node});
    }

    int node = best.second;
    if (node == -1) break;

    vis[node] = true;
    for (auto &e : adj[node]) {
      if (ans[node] > e.bad_time) continue;

      int64_t curr = ans[node] - e.cost;
      if (curr < 0) continue;
      if (curr > ans[e.to]) {
        ans[e.to] = curr;
        assert(!vis[e.to]);
      }
    }
  }
}

int64_t dist[N];

void Dijkstra(int start_node, int64_t start_time, int64_t day_size) {
  for (int i = 0; i < n; ++i) {
    vis[i] = false;
    dist[i] = INF_LL;
  }
  dist[start_node] = start_time;

  while (true) {
    pair<int64_t, int> best = {INF_LL, -1};

    for (int node = 0; node < n; ++node) {
      if (vis[node] || dist[node] == INF_LL) continue;
      best = min(best, {dist[node], node});
    }

    int node = best.second;
    if (node == -1) break;

    vis[node] = true;
    for (auto &e : adj[node]) {
      int64_t nt = dist[node] + e.cost;
      int64_t aux_t = dist[node] % day_size + e.cost;
      if (aux_t > e.bad_time)
        nt = (dist[node] + day_size - 1) / day_size * day_size + e.cost;
      if (nt < dist[e.to]) {
        dist[e.to] = nt;
        assert(!vis[e.to]);
      }
    }
  }
}

vector<int64_t> buckets[N];
vector<vector<int>> qrs[N];
}

vector<long long> calculate_necessary_time(int N, int m, long long day_size, int q, vector<int> A, vector<int> B, vector<long long> L, vector<long long> C, vector<int> U, vector<int> V, vector<long long> T) {

  n = N;
  for (int i = 0; i < m; ++i) {
    int a = A[i], b = B[i];
    int64_t l = L[i], c = C[i];
    adj[a].emplace_back(Edge{b, l, c});
    adj[b].emplace_back(Edge{a, l, c});
  }

//  vector<vector<int64_t>> buckets(n);
  for (int i = 0; i < n; ++i) {
    buckets[i].emplace_back(0);
    buckets[i].emplace_back(day_size);
  }

  for (int i = 0; i < m; ++i) {
    int64_t t = C[i] + 1 - L[i];
    int node = A[i];

    GetConstraints(node, t);
    for (int j = 0; j < n; ++j) {
      if (ans[j] >= 0) buckets[j].emplace_back(ans[j]);
    }

    node = B[i];
    GetConstraints(node, t);
    for (int j = 0; j < n; ++j) {
      if (ans[j] >= 0) buckets[j].emplace_back(ans[j]);
    }
  }

  for (int i = 0; i < n; ++i) {
    sort(buckets[i].begin(), buckets[i].end());
    buckets[i].erase(unique(buckets[i].begin(), buckets[i].end()), buckets[i].end());
  }

//  vector<vector<vector<int>>> qrs(n);
  for (int i = 0; i < n; ++i) {
    qrs[i].resize(buckets[i].size());
  }

  for (int i = 0; i < q; ++i) {
    int from = U[i];
    int64_t t = T[i];
    int pos = upper_bound(buckets[from].begin(), buckets[from].end(), t)
      - buckets[from].begin() - 1;
    qrs[from][pos].emplace_back(i);
  }

  vector<long long> res(q);
  for (int node = 0; node < n; ++node) {
    for (int j = 0; j + 1 < (int)buckets[node].size(); ++j) {
      int64_t t = buckets[node][j];
      if (qrs[node][j].empty()) continue;

      Dijkstra(node, t, day_size);
      for (int qid : qrs[node][j]) {
        int64_t curr = dist[V[qid]];
        if (curr > day_size) curr -= T[qid];
        else curr -= t;

        res[qid] = curr;
      }
    }
  }

  return res;
}