#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint inf = 1e18;
vector<lint> calculate_necessary_time(
int N, int M, lint S, int Q,
vector<int> A, vector<int> B,
vector<lint> L, vector<lint> C,
vector<int> U, vector<int> V, vector<lint> T) {
// Solution:
//
// First, we compute the minimum time between any 2 cities
// x and y, if we start from city x at time 0. We can
// compute this in O(N^3) with Dijkstra.
//
// Next, process each starting city independently.
// Generate the shortest path, assuming there is no restriction
// on roads, and day is indefinitely long. Then, there is an
// edge which is the "bottleneck" - the maximum time we can start
// at source to generate this particular shortest path tree.
// The bottleneck is the minimum C[i] - L[i] - dist[A[i]] if we
// use the i-th edge in shortest path tree to go from A[i] to B[i].
//
// After identifying the bottleneck, if we start at any time before
// the bottleneck, we can go to the other cities in time dist[v].
// After arriving at city v, we will have to wait until the next day,
// then start the journey again. However, we already computed the minimum
// time to go from any 2 cities if we start at time 0. Thus, we can
// process a single query by bruteforcing the city where we wait until
// the next day.
//
// Since after deleting a bottleneck, we recompute the shortest path tree,
// we need O(N^2) recomputations in O(N^2) time each. There are O(N) sources,
// and each query is done in O(N). This yields O(N^5 + Q N).
//
// To speed it up, for every vertex u, and edge adjacent to u, we calculate
// the minimum time to reach all vertices v in the same day. Then, instead
// of banning an edge, we add an edge instead by sweeping backwards.
// Observet the condition when banning an edge: the minimum C[i] - L[i] - dist[i].
// For all edges e adjacent to u, we sort them by C[e] - L[e]. Then, for every vertex,
// we only need to consider a single edge (the largest C[e] - L[e]), and add them one
// by one. This can be done via a priority queue or segment tree. Then, after getting
// the maximum edge e, we reupdate all distances in O(N).
//
// Time complexity: O(N^4 log N + Q N).
M = M + M;
for (int i = 0; i < M / 2; i++) {
A.push_back(B[i]);
B.push_back(A[i]);
L.push_back(L[i]);
C.push_back(C[i]);
}
vector<vector<int>> adj(N);
for (int i = 0; i < M; i++) {
adj[A[i]].push_back(i);
}
const auto Dijkstra = [&](int s, vector<lint> &dist, lint init) {
dist.assign(N, inf);
vector<int> done(N);
dist[s] = init;
for (int rep = 0; rep < N; rep++) {
int u = -1;
for (int v = 0; v < N; v++) if (!done[v]) {
if (u == -1 || dist[u] > dist[v]) {
u = v;
}
}
if (dist[u] == inf) {
break;
}
done[u] = 1;
for (auto e : adj[u]) {
int v = B[e];
if ((dist[u] % S) <= C[e] - L[e]) {
dist[v] = min(dist[v], dist[u] + L[e]);
} else {
dist[v] = min(dist[v], dist[u] + (S - dist[u] % S) % S + L[e]);
}
}
}
};
// distance between cities (i, v) if we start at time 0.
vector<vector<lint>> dist0(N, vector<lint>(N, inf));
for (int s = 0; s < N; s++) {
Dijkstra(s, dist0[s], 0);
}
// distance between cities (A[i], v) if we start at time C[e] - L[e]
// must arrive at same day
vector<vector<lint>> distE(M, vector<lint>(N));
for (int e = 0; e < M; e++) {
Dijkstra(A[e], distE[e], C[e] - L[e]);
for (int i = 0; i < N; i++) {
if (distE[e][i] < S) {
distE[e][i] -= C[e] - L[e];
} else {
distE[e][i] = inf;
}
}
}
for (int u = 0; u < N; u++) {
sort(begin(adj[u]), end(adj[u]), [&](int i, int j) {
return C[i] - L[i] > C[j] - L[j];
});
}
vector<vector<int>> queries(N);
for (int q = 0; q < Q; q++) {
queries[U[q]].emplace_back(q);
}
vector<lint> ans(Q, inf);
for (int s = 0; s < N; s++) {
auto &query = queries[s];
sort(begin(query), end(query), [&](int i, int j) {
return T[i] < T[j];
});
vector<int> ptr(N);
vector<lint> dist(N, inf);
dist[s] = 0;
// Segment Tree
vector<pair<lint, int>> tree(2 * N, {-1, -1});
const auto Update = [&](int p, lint x) {
const pair<lint, int> val = {x, p};
tree[p += N] = val;
for (p /= 2; p > 0; p /= 2) {
tree[p] = max(tree[p * 2], tree[p * 2 + 1]);
}
};
const auto Query = [&](int l, int r) {
pair<lint, int> res = {-1, -1};
for (l += N, r += N; l < r; l /= 2, r /= 2) {
if (l & 1) res = max(res, tree[l++]);
if (r & 1) res = max(res, tree[--r]);
}
return res;
};
Update(s, C[adj[s][ptr[s]]] - L[adj[s][ptr[s]]]);
while (true) {
auto top = Query(0, N);
lint cur_time = top.first;
while (!query.empty() && T[query.back()] > cur_time) {
int q = query.back(); query.pop_back();
for (int m = 0; m < N; m++) { // answer query, brute force when first day ends
ans[q] = min(ans[q], dist[m] + (m != V[q]) * ((S - (dist[m] + T[q]) % S) % S) + dist0[m][V[q]]);
}
}
if (cur_time < 0) break;
int u = top.second;
int e = adj[u][ptr[u]];
ptr[u]++;
if (ptr[u] < adj[u].size()) {
Update(u, C[adj[u][ptr[u]]] - L[adj[u][ptr[u]]] - dist[u]);
} else {
Update(u, -1);
}
assert(u == A[e]);
for (int v = 0; v < N; v++) if (distE[e][v] != inf) {
if (dist[v] < dist[u] + distE[e][v]) {
dist[v] = dist[u] + distE[e][v];
if (ptr[v] < adj[v].size()) {
Update(v, min(cur_time, C[adj[v][ptr[v]]] - L[adj[v][ptr[v]]] - dist[v]));
}
}
}
}
}
return ans;
}
Compilation message
escape_route.cpp: In function 'std::vector<long long int> calculate_necessary_time(int, int, lint, 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:167:18: 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]
167 | if (ptr[u] < adj[u].size()) {
escape_route.cpp:177:22: 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]
177 | if (ptr[v] < adj[v].size()) {
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
64988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3444 ms |
113092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
64988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
64988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
64988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
