#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
void chk(ll &x, ll y) {
if (x > y) x = y;
}
vector<ll> calculate_necessary_time(int n, int m, ll S, int q,
vector<int> A, vector<int> B, vector<ll> L, vector<ll> C,
vector<int> U, vector<int> V, vector<ll> T) {
vector<vector<ll>> W(n, vector<ll>(n, -1)), lim = W;
for (int i = 0; i < m; i++) {
W[A[i]][B[i]] = W[B[i]][A[i]] = L[i];
lim[A[i]][B[i]] = lim[B[i]][A[i]] = C[i] - L[i];
}
auto dijkstra = [&](vector<ll> &d) {
vector<bool> vis(n);
while (1) {
int u = -1;
for (int i = 0; i < n; i++) {
if (!vis[i] && d[i] < INF && (!~u || d[u] > d[i])) u = i;
}
if (!~u) break;
vis[u] = 1;
for (int i = 0; i < n; i++) if (~W[u][i]) {
if (d[u] % S <= lim[u][i]) chk(d[i], d[u] + W[u][i]);
else chk(d[i], (d[u] + S - 1) / S * S + W[u][i]);
}
}
};
vector<vector<ll>> dv(n, vector<ll>(n, INF));
vector<vector<vector<ll>>> de(n, dv);
for (int i = 0; i < n; i++) {
dv[i][i] = 0, dijkstra(dv[i]);
for (int j = 0; j < n; j++) if (~W[i][j]) {
de[i][j][i] = lim[i][j], dijkstra(de[i][j]);
for (int k = 0; k < n; k++) {
de[i][j][k] = de[i][j][k] < S ? de[i][j][k] - lim[i][j] : INF;
}
}
}
vector<vector<int>> G(n), Q(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (~W[i][j]) G[i].push_back(j);
}
sort(G[i].begin(), G[i].end(), [&](int x, int y) { return lim[i][x] > lim[i][y]; });
}
vector<ll> ans(q, INF);
for (int i = 0; i < q; i++) {
Q[U[i]].push_back(i);
}
for (int s = 0; s < n; s++) {
sort(Q[s].begin(), Q[s].end(), [&](int x, int y) { return T[x] < T[y]; });
vector<int> cur(n);
vector<ll> dist(n, INF), tim(n, -1);
dist[s] = 0, tim[s] = lim[s][G[s][0]];
while (1) {
int u = max_element(tim.begin(), tim.end()) - tim.begin();
for (; !Q[s].empty() && T[Q[s].back()] > tim[u]; Q[s].pop_back()) {
int k = Q[s].back();
for (int i = 0; i < n; i++) {
chk(ans[k], dist[i] + (i != V[k] ? (S - (dist[i] + T[k]) % S) % S : 0) + dv[i][V[k]]);
}
}
if (!~tim[u]) break;
int v = G[u][cur[u]++];
tim[u] = cur[u] < G[u].size() ? lim[u][G[u][cur[u]]] - dist[u] : -1;
for (int i = 0; i < n; i++) if (dist[i] > dist[u] + de[u][v][i]) {
dist[i] = dist[u] + de[u][v][i];
if (cur[i] < G[i].size()) tim[i] = min(tim[u], lim[i][G[i][cur[i]]] - dist[i]);
}
}
}
return ans;
}
Compilation message
escape_route.cpp: In function 'std::vector<long long int> calculate_necessary_time(int, int, ll, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<long long int>, std::vector<int>, std::vector<int>, std::vector<long long int>)':
escape_route.cpp:72:29: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | tim[u] = cur[u] < G[u].size() ? lim[u][G[u][cur[u]]] - dist[u] : -1;
escape_route.cpp:75:28: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | if (cur[i] < G[i].size()) tim[i] = min(tim[u], lim[i][G[i][cur[i]]] - dist[i]);
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
65048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2114 ms |
113784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
65048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
65048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
65048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
