// ~Be name khoda~ //
#include "escape_route.h"
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define cl clear
#define endll '\n'
const int maxn = 1e6 + 10;
const int maxn5 = 91;
const int maxq = 3e6 + 5;
const int maxe = 4e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 2e18;
ll t[maxq], c[maxe], l[maxe];
int u[maxq], v[maxq];
int a[maxe], b[maxe];
int n, m, q;
ll s, ans[maxq], mn, tim[maxn5];
bool ok[maxn5], done[maxn5];
ll dis[maxn5], with0[maxn5][maxn5];
int adj[maxn5][maxn5];
vector <int> av[maxn5];
inline bool cmp(int i, int j){return t[i] < t[j];}
inline void fix(ll &a){
if(a >= s)
a -= s;
}
inline void dij(int v, ll ti){
//cout << "hola " << v << ' ' << ti << endl;
memset(dis, -1, sizeof dis);
memset(done, false, sizeof done);
memset(ok, false, sizeof ok);
dis[v] = 0;
tim[v] = ti;
ok[v] = true;
mn = inf;
for(int i = 0; i < n; i++){
int v = -1;
for(int j = 0; j < n; j++) if(!done[j] && dis[j] > -1 && (v == -1 || dis[j] < dis[v])){
v = j;
}
done[v] = true;
//cout << "ok " << v << ' ' << dis[v] << ' ' << tim[v] << endl;
for(int j = 0; j < n; j++) if(adj[v][j] != -1 && !done[j]){
ll len;
if(tim[v] <= c[adj[v][j]] - l[adj[v][j]]){
if(ok[v]){
ok[j] = true;
mn = min(mn, c[adj[v][j]] - l[adj[v][j]] - tim[v]);
}
len = l[adj[v][j]];
}
else{
len = s - tim[v] + l[adj[v][j]];
}
//cout << v << ' ' << j << ' ' << len << ' ' << adj[v][j] << ' ' << l[adj[v][j]] << endl;
if(dis[j] == -1 || dis[j] > dis[v] + len){
dis[j] = dis[v] + len;
tim[j] = tim[v] + len;
fix(tim[j]);
}
}
}
return;
}
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) {
n = N;
m = M;
s = S;
q = Q;
memset(adj, -1, sizeof adj);
for(int i = 0; i < m; i++){
a[i] = A[i];
b[i] = B[i];
l[i] = L[i];
c[i] = C[i];
adj[a[i]][b[i]] = adj[b[i]][a[i]] = i;
}
for(int i = 0; i < q; i++){
u[i] = U[i];
v[i] = V[i];
t[i] = T[i];
av[u[i]].pb(i);
}
//*
for(int i = 0; i < n; i++){
dij(i, 0);
for(int j = 0; j < n; j++)
with0[i][j] = dis[j];
}
//*/
for(int i = 0; i < n; i++){
sort(all(av[i]), cmp);
ll last = 0;
dij(i, 0);
for(auto j : av[i]){
if(rng() % 5 > 0 && mn < t[j] - last){
last = t[j];
dij(i, last);
ans[j] = dis[v[j]];
}
else{
mn -= (t[j] - last);
ans[j] = inf;
for(int z = 0; z < n; z++) if(ok[z]){
if(z == v[j])
ans[j] = min(ans[j], dis[z]);
ans[j] = min(ans[j], dis[z] + s - (tim[z] + (t[j] - last)) + with0[z][v[j]]);
}
}
}
}
vector <long long> ret;
for(int i = 0; i < q; i++)
ret.pb(ans[i]);
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
64932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2117 ms |
188532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
64932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
64932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
64932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
