#include "escape_route.h"
#include <algorithm>
#include <iostream>
using std::vector;
using std::pair;
using ll = long long;
const ll INF = 1e18;
vector<ll> dijkstra(int N, ll S, int st, ll T, vector<vector<ll>> &l, vector<vector<ll>> &c) {
vector<ll> t(N, INF);
vector<bool> used(N, 0);
t[st] = T;
for (int it = 0; it < N; ++it) {
int u = -1;
for (int i = 0; i < N; ++i) {
if (!used[i] && (u == -1 || t[i] < t[u]))
u = i;
}
if (t[u] == INF) break;
used[u] = 1;
for (int v = 0; v < N; ++v) {
if (!used[v] && l[u][v] < S) {
ll t1 = t[u] + l[u][v];
if (t[u] % S + l[u][v] > c[u][v])
t1 += S - t1 % S;
t[v] = std::min(t[v], t1);
}
}
}
return t;
}
vector<long long> calculate_necessary_time(
int N, int M, long long S, int Q, vector<int> A, vector<int> B,
vector<long long> L, vector<long long> C, vector<int> U,
vector<int> V, vector<long long> T) {
vector<vector<ll>> l(N, vector<ll>(N, S));
vector<vector<ll>> c(N, vector<ll>(N, S));
for (int i = 0; i < M; ++i) {
l[A[i]][B[i]] = l[B[i]][A[i]] = L[i];
c[A[i]][B[i]] = c[B[i]][A[i]] = C[i];
}
for (int i = 0; i < N; ++i) {
l[i][i] = 0;
c[i][i] = 0;
}
vector<vector<vector<ll>>> t(N, vector<vector<ll>>(N));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (l[i][j] < S)
t[i][j] = dijkstra(N, S, j, c[i][j], l, c);
}
}
vector<ll> ans(Q);
for (int i = 0; i < Q; ++i) {
ans[i] = t[U[i]][U[i]][V[i]] + (S - T[i]) % S;
}
for (int st = 0; st < N; ++st) {
vector<pair<ll, int>> que;
for (int i = 0; i < Q; ++i) {
if (U[i] == st)
que.push_back({T[i], i});
}
std::sort(que.rbegin(), que.rend());
vector<vector<pair<ll, int>>> ord(N);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (i != j && l[i][j] < S)
ord[i].push_back({c[i][j] - l[i][j], j});
}
std::sort(ord[i].rbegin(), ord[i].rend());
}
vector<int> ind(N, 0);
vector<ll> d(N, INF);
d[st] = 0;
int ptr = 0;
while (1) {
pair<ll, int> max = {-1, -1};
for (int i = 0; i < N; ++i) {
if (ind[i] < ord[i].size())
max = std::max(max, {ord[i][ind[i]].first - d[i], i});
}
while (ptr < que.size() && que[ptr].first > max.first) {
int id = que[ptr++].second;
// std::cerr << id << " " << d[V[id]] << "\n";
ans[id] = std::min(ans[id], d[V[id]]);
for (int i = 0; i < N; ++i) {
if (d[i] < INF)
ans[id] = std::min(ans[id], S - T[id] + t[i][i][V[id]]);
}
}
if (max.first < 0) break;
int u = max.second;
int v = ord[u][ind[u]++].second;
for (int i = 0; i < N; ++i) {
if (t[u][v][i] < S)
d[i] = std::min(d[i], t[u][v][i] - max.first);
}
}
}
return ans;
}
Compilation message
escape_route.cpp: In function 'std::vector<long long int> calculate_necessary_time(int, int, long long int, 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:84:16: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | if (ind[i] < ord[i].size())
escape_route.cpp:87:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | while (ptr < que.size() && que[ptr].first > max.first) {
| ~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
64980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1273 ms |
137076 KB |
Output is correct |
| 2 |
Correct |
1334 ms |
189252 KB |
Output is correct |
| 3 |
Correct |
1278 ms |
178792 KB |
Output is correct |
| 4 |
Correct |
1329 ms |
197840 KB |
Output is correct |
| 5 |
Correct |
1323 ms |
197880 KB |
Output is correct |
| 6 |
Incorrect |
22 ms |
64980 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
64980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
64980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
64980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
