#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(int i=0; i<M; ++i) K[i] = C[i] - L[i]; vector<ll> ans(Q); vector<vector<ll>> queries(N); for(int i=0; i<Q; ++i) { queries[U[i]].push_back(i); } vector<vector<pair<int, int>>> g(N); for(int 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 get_dists = [&](int s) { vector<ll> dist(N, inf), vis(N,0); dist[s] = 0; while(1) { pair<ll, ll> best = {inf,0}; for(int 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; }; vector<vector<ll>> dist(N); for(int i=0; i<N; ++i) dist[i] = get_dists(i); for(int i=0; i<N; ++i) sort(g[i].begin(), g[i].end(), [&](pair<int, int> x, pair<int, int> y){ return K[x.second] < K[y.second]; }); vector<vector<pair<int, int>>> oldg = g; for(int s=0; s<N; ++s) { g = oldg; sort(queries[s].begin(), queries[s].end(), [&](ll i, ll j) { return T[i] > T[j]; }); vector<ll> best(M, S), parent(M); vector<ll> green; vector<set<int>> got(M); auto zmien = [&](ll x, ll diff){ queue<int> pq; pq.push(x); while(pq.size()) { int v = pq.front(); pq.pop(); best[v] -= diff; for(auto u : got[v]) pq.push(u); } }; green.push_back(s); best[s] = S; for(auto idx : queries[s]) { ll res = inf; ll diff = best[s] - T[idx]; for(auto x : green) best[x] -= diff; queue<int> Q; for(auto x : green) Q.push(x); while(Q.size()) { int x = Q.front(); Q.pop(); while(g[x].size()) { auto[u,i] = g[x].back(); if(best[x] <= K[i]) { if(best[u]==S) { green.push_back(u); } Q.push(u); if(best[u] > best[x] + L[i]) { ll DD = best[u] - (best[x] + L[i]); zmien(u,DD); got[parent[u]].erase(u); got[x].insert(u); parent[u] = x; } g[x].pop_back(); } else break; } } // for(int i=0; i<N; ++i) cout << best[i] << " "; cout << "\n"; for(auto x : green) { if(x==V[idx]) { res = min(res, best[x]); } res = min(res, (best[x]==0 ? 0 : S) + dist[x][V[idx]]); } ans[idx] = res - T[idx]; } } return ans; }