#include "escape_route.h"
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n';
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
const int N = 42;
const ll Inf = 1e18;
int n, m;
ll S;
vi A, B;
vl L, C;
vector<int> G[N];
ll dj_dis[N], dj_mk[N];
void Djik(int src, ll st){
memset(dj_dis, 31, sizeof dj_dis);
memset(dj_mk, 0, sizeof dj_mk);
dj_dis[src] = st;
int adj;
ll w;
for(int _ = 0; _ < n; _++){
int idx = -1;
for(int i = 0; i < n; i++) if(!dj_mk[i]) idx = i;
if(idx == -1) continue;
for(int i = 0; i < n; i++) if(!dj_mk[i] && dj_dis[i] < dj_dis[idx]) idx = i;
dj_mk[idx] = 1;
for(auto e : G[idx]){
adj = A[e] ^ B[e] ^ idx;
if(dj_dis[idx] % S <= C[e] - L[e])
w = dj_dis[idx] + L[e];
else
w = dj_dis[idx] + (S - (dj_dis[idx] % S)) + L[e];
if(w < dj_dis[adj])
dj_dis[adj] = w;
}
}
}
ll dis0[N][N];
ll dis[N][N * N][N]; // u. no of (good) act. adj
ll tim[N][N * N], po[N]; //u. no of act.
int mk[N][N * N]; // u id_e
int Get(int u, ll st){
int L = -1, R = po[u] + 1, mid;
while(L + 1 < R){
mid = (L + R) >> 1;
if(tim[u][mid] >= st) L = mid;
else R = mid;
}
assert(L != -1);
return L;
}
pll Calc(int u){
ll mn = S + 1;
int idx = -1;
for(int v = 0; v < n; v++){
if(dis[u][ po[u] ][v] > S) continue;
for(auto e : G[v]){
if(mk[u][e]) continue;
ll wt = dis[u][ po[u] ][v] - (C[e] - L[e]);
wt = max(wt, 0ll);
if(wt < mn){
mn = wt;
idx = e;
}
}
}
return pll(idx == -1 ? S + 1 : tim[u][po[u]] - mn, idx);
}
ll nw_dis[N];
bool Step(){
pair<pll, int> bst = {pll(-1, -1), -1};
for(int i = 0; i < n; i++){
auto res = Calc(i);
if(res.S == -1) continue;
bst = max(bst, {Calc(i), i});
}
if(bst.S == -1) return false;
int u = bst.S;
int ed = bst.F.S;
ll del = tim[u][po[u]] - bst.F.F;
mk[u][ed] = 1;
// if(u == 0){
// cerr << "&& " << A[ed] << ' ' << B[ed] << '\n';
// }
if(tim[u][ po[u] ] < del)
return true;
// cerr << "******* " << u << ' ' << tim[u][po[u]] - del << '\n';
fill(nw_dis, nw_dis + N, S + 1);
// old
for(int i = 0; i < n; i++)
if(dis[u][po[u]][i] != S + 1)
nw_dis[i] = min(nw_dis[i], dis[u][ po[u] ][i] - del);
int fr = A[ed], to = B[ed];
if(nw_dis[fr] > nw_dis[to]) swap(fr, to);
int lay = Get(to, C[ed]);
// if(u == 0 && (ed == 0 || ed == 2)){
// debug(to);
// debug(dis[to][lay][to]);
// debug(C[ed]);
// debug(tim[to][lay]);
// }
for(int i = 0; i < n; i++)
if(dis[to][lay][i] <= S)
nw_dis[i] = min(nw_dis[i], dis[to][lay][i] - (tim[to][lay] - C[ed]));
po[u] ++;
tim[u][po[u]] = tim[u][po[u] - 1] - del;
for(int i = 0; i < n; i++)
dis[u][po[u]][i] = nw_dis[i];
return true;
}
vl calculate_necessary_time(int _n, int _m, ll _S, int Q, vi _A, vi _B, vl _L, vl _C, vi _U, vi _V, vl _T) {
n = _n; m = _m; S = _S;
A = _A; B = _B; L = _L; C = _C;
for(int i = 0; i < m; i++)
G[A[i]].pb(i), G[B[i]].pb(i);
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
fill(dis[i][j], dis[i][j] + n, S + 1);
for(int i = 0; i < n; i++){
po[i] = 0;
tim[i][0] = S;
dis[i][0][i] = S;
}
while(Step()) ;
for(int i = 0; i < n; i++){
Djik(i, 0);
for(int j = 0; j < n; j++)
dis0[i][j] = dj_dis[j];
}
vl ANS;
// for(int i = 0; i <= po[0]; i++){
// cerr << "lay : " << tim[0][i] << '\n';
// cerr << "! ";
// for(int j = 0; j < n; j++)
// cerr << dis[0][i][j] << ' ';
// cerr << '\n';
// }
for(int i = 0; i < Q; i++){
int lay = Get(_U[i], _T[i]);
// if(i == 0){
// debug(tim[_U[i]][lay]);
// debug(dis[_U[i]][lay][_V[i]]);
// // Djik(_U[i], _T[i]);
// debug(tim[_U[i]][lay] - _T[i]);
// }
if(dis[_U[i]][lay][_V[i]] <= S)
ANS.pb((dis[_U[i]][lay][_V[i]] - (tim[_U[i]][lay] - _T[i])) - _T[i]);
else {
ll res = Inf;
for(int j = 0; j < n; j++){
if(dis[_U[i]][lay][j] <= S){
res = min(res, S - _T[i] + dis0[j][_V[i]]);
}
}
ANS.pb(res);
}
// ANS.pb(dis[_V[i]] - _T[i]);
}
return ANS;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
64964 KB |
Output is correct |
| 2 |
Correct |
303 ms |
64968 KB |
Output is correct |
| 3 |
Execution timed out |
9006 ms |
65092 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9032 ms |
111948 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
64964 KB |
Output is correct |
| 2 |
Correct |
303 ms |
64968 KB |
Output is correct |
| 3 |
Execution timed out |
9006 ms |
65092 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
64964 KB |
Output is correct |
| 2 |
Correct |
303 ms |
64968 KB |
Output is correct |
| 3 |
Execution timed out |
9006 ms |
65092 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
64964 KB |
Output is correct |
| 2 |
Correct |
303 ms |
64968 KB |
Output is correct |
| 3 |
Execution timed out |
9006 ms |
65092 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
