#include "escape_route.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
struct edg{
int pos;
lint L, C;
};
struct node{
int i, j; lint max_time;
bool operator<(const node &n)const{
return max_time < n.max_time;
}
};
lint daybreak[96][96];
lint dayfinish[96][96];
lint adj[96][96], dp[96][96];
vector<edg> gph[96];
vector<pi> qq[96][96];
vector<pi> prec[96][96];
lint ret[2000005];
lint S;
void Do(int u, int n){
for(auto &e : gph[u]){
int v = e.pos;
vector<lint> dist1(n, -3e18), dist2(n, 3e18);
// backward shortest path
{
dist1[u] = e.C - e.L;
vector<int> vis(n);
for(int it = 0; it < n; it++){
pi ret(-5e18, 5e18);
for(int i = 0; i < n; i++){
if(!vis[i]) ret = max(ret, pi(dist1[i], i));
}
if(ret.first < 0) break;
int x = ret.second;
vis[x] = 1;
for(auto &e : gph[x]){
if(dist1[e.pos] < dist1[x] - e.L && dist1[x] < e.C){
dist1[e.pos] = dist1[x] - e.L;
}
}
}
}
// forward shortest path
{
dist2[v] = e.C;
vector<int> vis(n);
for(int it = 0; it < n; it++){
pi ret(5e18, 5e18);
for(int i = 0; i < n; i++){
if(!vis[i]) ret = min(ret, pi(dist2[i], i));
}
int x = ret.second;
if(ret.first > S) break;
vis[x] = 1;
for(auto &e : gph[x]){
if(dist2[e.pos] > dist2[x] + e.L && dist2[x] + e.L <= e.C){
dist2[e.pos] = dist2[x] + e.L;
}
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(dist2[j] <= S && dist1[i] >= 0){
prec[i][j].emplace_back(dist1[i], dist2[j] - dist1[i]);
}
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
sort(all(prec[i][j]));
int ptr = sz(prec[i][j]);
lint curMin = 1e18;
for(auto &[x, y] : qq[i][j]){
while(ptr > 0 && prec[i][j][ptr - 1].first >= x){
curMin = min(curMin, prec[i][j][--ptr].second);
}
ret[y] = min(ret[y], curMin);
}
prec[i][j].clear();
}
}
}
// wtf just use namespace std and pairs
std::vector<long long> calculate_necessary_time(
int N, int M, long long Sfuck, 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) {
S = Sfuck;
for(int i = 0; i < M; i++){
gph[A[i]].push_back({B[i], L[i], C[i]});
gph[B[i]].push_back({A[i], L[i], C[i]});
}
{
priority_queue<node> pq;
memset(daybreak, 0x3f, sizeof(daybreak));
auto enq = [&](int s, int e, lint x){
if(daybreak[s][e] > x){
daybreak[s][e] = x;
pq.push({s, e, -x});
}
};
for(int i = 0; i < N; i++){
enq(i, i, 0);
}
while(sz(pq)){
auto x = pq.top(); pq.pop();
x.max_time = -x.max_time;
if(daybreak[x.i][x.j] != x.max_time) continue;
for(auto &e : gph[x.j]){
if(x.max_time + e.L <= e.C){
enq(x.i, e.pos, x.max_time + e.L);
}
}
}
}
{
priority_queue<node> pq;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
dayfinish[i][j] = -1e18;
}
}
auto enq = [&](int s, int e, lint x){
if(dayfinish[s][e] < x){
dayfinish[s][e] = x;
pq.push({s, e, x});
}
};
for(int i = 0; i < N; i++){
enq(i, i, S);
}
while(sz(pq)){
auto x = pq.top(); pq.pop();
if(dayfinish[x.i][x.j] != x.max_time) continue;
for(auto &e : gph[x.i]){
lint val = min(x.max_time, e.C) - e.L;
if(val >= 0) enq(e.pos, x.j, val);
}
}
}
{
memset(adj, 0x3f, sizeof(adj));
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(dayfinish[i][j] >= 0) adj[i][j] = 1;
if(i == j) adj[i][j] = 0;
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
for(int k = 0; k < N; k++){
adj[j][k] = min(adj[j][k], adj[j][i] + adj[i][k]);
}
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
assert(adj[i][j] <= N);
dp[i][j] = 1e18;
for(int k = 0; k < N; k++){
dp[i][j] = min(adj[i][k] * S + daybreak[k][j], dp[i][j]);
}
}
}
}
fill(ret, ret + Q, 1e18);
for(int i = 0; i < Q; i++){
qq[U[i]][V[i]].emplace_back(T[i], i);
}
for(int i = 0; i < Q; i++){
for(int j = 0; j < N; j++){
if(dayfinish[U[i]][j] >= T[i]){
ret[i] = min(ret[i], S - T[i] + dp[j][V[i]]);
}
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
sort(all(qq[i][j]));
reverse(all(qq[i][j]));
}
}
for(int i = 0; i < N; i++){
Do(i, N);
}
vector<lint> ans(ret, ret + Q);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
65468 KB |
Output is correct |
| 2 |
Correct |
37 ms |
65476 KB |
Output is correct |
| 3 |
Correct |
118 ms |
65460 KB |
Output is correct |
| 4 |
Correct |
34 ms |
65372 KB |
Output is correct |
| 5 |
Correct |
40 ms |
65392 KB |
Output is correct |
| 6 |
Correct |
36 ms |
65564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
207 ms |
130108 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
65468 KB |
Output is correct |
| 2 |
Correct |
37 ms |
65476 KB |
Output is correct |
| 3 |
Correct |
118 ms |
65460 KB |
Output is correct |
| 4 |
Correct |
34 ms |
65372 KB |
Output is correct |
| 5 |
Correct |
40 ms |
65392 KB |
Output is correct |
| 6 |
Correct |
36 ms |
65564 KB |
Output is correct |
| 7 |
Runtime error |
207 ms |
130108 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
65468 KB |
Output is correct |
| 2 |
Correct |
37 ms |
65476 KB |
Output is correct |
| 3 |
Correct |
118 ms |
65460 KB |
Output is correct |
| 4 |
Correct |
34 ms |
65372 KB |
Output is correct |
| 5 |
Correct |
40 ms |
65392 KB |
Output is correct |
| 6 |
Correct |
36 ms |
65564 KB |
Output is correct |
| 7 |
Runtime error |
207 ms |
130108 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
65468 KB |
Output is correct |
| 2 |
Correct |
37 ms |
65476 KB |
Output is correct |
| 3 |
Correct |
118 ms |
65460 KB |
Output is correct |
| 4 |
Correct |
34 ms |
65372 KB |
Output is correct |
| 5 |
Correct |
40 ms |
65392 KB |
Output is correct |
| 6 |
Correct |
36 ms |
65564 KB |
Output is correct |
| 7 |
Runtime error |
207 ms |
130108 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
