#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 95;
const ll INF = 1e18;
ll mint[MAXN][MAXN];//mint[i][j] =def= the minimum time to get from i to j, knowing that you start at time 0 in node i
ll invt[MAXN][MAXN];
struct info
{
vector<pair<ll,ll>> important = {};//{start_time, time_needed}
//dp[nod][t] = what is the earliest we can reach dest starting from nod at time t
//what works for t also works for smaller ts
void init()
{
important.clear();
}
ll query(ll t)
{
auto it = lower_bound(important.begin(), important.end(), make_pair(t, -1LL));
if(it == important.end())
return INF;
else
return (*it).second;
}
};
void afis(info x)
{
for(auto u:x.important)
cerr<<u.first<<" "<<u.second<<"\n";
cerr<<"important\n\n";
}
info combine(info x, info y)
{
if(x.important.empty())
return y;
if(y.important.empty())
return x;
/*cerr<<"combine these:\n";
afis(x);
afis(y);*/
vector<pair<ll,ll>> aux;
for(auto it:x.important)
aux.push_back(it);
for(auto it:y.important)
aux.push_back(it);
sort(aux.begin(), aux.end());
//fa interclasare ca sa scapi de log-------------------------------------------------------------------
info rez;
ll mnm = INF;
for(int i=(int)aux.size()-1;i>=0;i--)
{
if(aux[i].second < mnm && (i == 0 || aux[i].first != aux[i-1].first))
{
mnm = aux[i].second;
rez.important.push_back(aux[i]);
}
}
reverse(rez.important.begin(), rez.important.end());
/*cerr<<"into this:\n";
afis(rez);
cerr<<"\n\n\n";*/
return rez;
}
info apply_edge(info x, ll L, ll C)
{
if(x.important.empty())
return x;
//cerr<<"initial:\n";afis(x);
info rez;
for(auto it:x.important)
{
if(it.first - L >= 0)
{
if(it.first < C)
{
rez.important.push_back({it.first - L, it.second + L});
}
else
{
rez.important.push_back({C - L, it.second + L});
break;
}
}
}
/*cerr<<"after applying "<<L<<" "<<C<<":\n";
afis(rez);
cerr<<"\n\n\n";*/
return rez;
}
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)
{
for(int i=0;i<M;i++)
assert(C[i] - L[i] >= 0);
for(int dest=0;dest<N;dest++)
{
for(int i=0;i<N;i++)
invt[i][dest] = -1;
invt[dest][dest] = S - 1;
for(int pas=0;pas<N;pas++)
{
for(int i=0;i<M;i++)
{
for(auto [a,b] : vector<pair<int,int>>{{A[i], B[i]}, {B[i], A[i]}})
{
ll myt = min(invt[b][dest], C[i]);
if(myt - L[i] >= 0)
invt[a][dest] = max(invt[a][dest], myt - L[i]);
}
}
}
}
/*for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
cerr<<i<<" "<<j<<": "<<invt[i][j]<<" invt\n";*/
for(int src=0;src<N;src++)
{
for(int i=0;i<N;i++)
mint[src][i] = INF;
mint[src][src] = 0;
for(int pas=0;pas<N;pas++)
{
for(int i=0;i<M;i++)
{
for(auto [a,b] : vector<pair<int,int>>{{A[i], B[i]}, {B[i], A[i]}})
{
if(mint[src][a] % S <= C[i] - L[i])
{
mint[src][b] = min(mint[src][b], mint[src][a] + L[i]);
}
else
{
mint[src][b] = min(mint[src][b], (mint[src][a] + (S - mint[src][a] % S)) + L[i]);
}
}
}
}
}
vector<ll> ans(Q, INF);
vector<vector<int>> qrys_of(N);
for(int i=0;i<Q;i++)
{
if(invt[U[i]][V[i]] >= T[i])//this is the only problem-----------------------
{
qrys_of[V[i]].push_back(i);
continue;
}
for(int stop=0;stop<N;stop++)
{
if(stop == V[i])
continue;
if(invt[U[i]][stop] >= T[i])
{
ll until_stop = S - T[i];
ll after_stop = mint[stop][V[i]];
ans[i] = min(ans[i], until_stop + after_stop);
}
}
}
return ans;
vector<info> dp(N);
for(int dest=0;dest<N;dest++)
{
if(qrys_of[dest].empty())
continue;
for(int i=0;i<N;i++)
dp[i].init();
dp[dest].important.push_back({S - 1, 0});
for(int pas=0;pas<N;pas++)
{
for(int i=0;i<M;i++)
{
for(auto [a,b] : vector<pair<int,int>>{{A[i], B[i]}, {B[i], A[i]}})
{
dp[a] = combine(dp[a], apply_edge(dp[b], L[i], C[i]));
}
}
}
/*for(int i=0;i<N;i++)
{
cerr<<dest<<" & "<<i<<" dp[i]:\n";
afis(dp[i]);
}*/
for(int qid:qrys_of[dest])
{
ans[qid] = min(ans[qid], dp[U[qid]].query(T[qid]));
}
}
return ans;
}
