#include "escape_route.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; std::vector<long long> calculate_necessary_time( int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B, std::vector<long long> L, std::vector<long long> C, std::vector<int> U, std::vector<int> V, std::vector<long long> T) { vector<ll> K(M); for(ll i=0; i<M; ++i) K[i] = C[i] - L[i]; vector<ll> ans(Q); vector<vector<vector<ll>>> queries(N, vector<vector<ll>>(N)); for(ll i=0; i<Q; ++i) { queries[U[i]][V[i]].push_back(i); } vector<vector<pair<ll, ll>>> g(N); for(ll i=0; i<M; ++i) { g[A[i]].push_back({B[i], i}); g[B[i]].push_back({A[i], i}); } ll inf = 1e18; auto dijkstra_min = [&](ll s, ll val) { vector<ll> dist(N, inf), vis(N,0); dist[s] = val; while(1) { pair<ll, ll> best = {inf,0}; for(ll i=0; i<N; ++i) if(!vis[i]) best = min(best, {dist[i], i}); if(best.first == inf) break; auto[dv,v] = best; vis[v] = 1; for(auto[u,k] : g[v]) { ll w = L[k]; ll t = dv%S; if(t > K[k]) w += S-t; if(dist[u] > dist[v] + w) { dist[u] = dist[v] + w; } } } return dist; }; auto dijkstra_max = [&](ll s, ll val) { vector<ll> dist(N, -1), vis(N,0); dist[s] = val; while(1) { pair<ll, ll> best = {-1,0}; for(ll i=0; i<N; ++i) if(!vis[i]) best = max(best, {dist[i], i}); if(best.first == -1) break; auto[dv,v] = best; vis[v] = 1; for(auto[u,k] : g[v]) { ll nd = min(K[k], dv-L[k]); if(dist[u] < nd) { dist[u] = nd; } } } return dist; }; vector<vector<ll>> day0(N); for(ll i=0; i<N; ++i) day0[i] = dijkstra_max(i, S-1); vector<vector<ll>> dist(N); for(ll i=0; i<N; ++i) dist[i] = dijkstra_min(i, 0); vector<vector<ll>> DX(2*M), DY(2*M); for(int i=0; i<M; ++i) { DX[2*i] = dijkstra_max(A[i], K[i]); DX[2*i+1] = dijkstra_max(B[i], K[i]); DY[2*i] = dijkstra_min(B[i], C[i]); DY[2*i+1] = dijkstra_min(A[i], C[i]); } vector<int> edges; for(int i=0; i<2*M; ++i) edges.push_back(i); for(ll s=0; s<N; ++s) { sort(edges.begin(), edges.end(), [&](int i, int j) { return DX[i][s] > DX[j][s]; }); for(ll u=0; u<N; ++u) { sort(queries[s][u].begin(), queries[s][u].end(), [&](int i, int j) { return T[i] > T[j]; }); ll best = inf; int cnt = 0; for(auto idx : queries[s][u]) { while(cnt < edges.size()) { int i = edges[cnt]; if(DX[i][s] >= T[idx]) { if(DY[i][u] < S) best = min(best, DY[i][u] - DX[i][s]); // cout << DY[i][u] << " - " << DX[i][s] << "\n"; cnt++; } else break; } if(T[idx]==0) { ans[idx] = dist[s][u]; continue; } ans[idx] = inf; if(day0[u][s] < T[idx]) { for(int i=0; i<N; ++i) if(day0[i][s] >= T[idx]) ans[idx] = min(ans[idx], S + dist[i][u]); ans[idx] -= T[idx]; } else { ans[idx] = best; } } } } return ans; }