| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 935649 | 2024-02-29T10:22:47 Z | Pannda | Escape Route (JOI21_escape_route) | C++17 | 0 ms | 0 KB |
#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
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) {
const long long INF = 9e18;
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < m; i++) {
int u = A[i];
int v = B[i];
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
auto [f, g] = [&]() -> pair<vector<vector<vector<long long>>>, vector<vector<long long>>> {
vector<vector<vector<long long>>> f(n);
vector<vector<long long>> g(n);
for (int source = 0; source < n; source++) {
long long t = 0;
while (true) {
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
vector<long long> dist(n, INF);
vector<int> par(n, -1);
dist[source] = 0;
pq.push({dist[source], source});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue;
for (auto [v, i] : adj[u]) {
if (t + dist[u] > C[i] - L[i]) continue;
if (dist[u] + L[i] < dist[v]) {
dist[v] = dist[u] + L[i];
par[v] = i;
pq.push({dist[v], v});
}
}
}
f[source].push_back(dist);
g[source].push_back(t);
long long new_t = INF;
for (int u = 0; u < n; u++) {
if (par[u] == -1) continue;
new_t = min(new_t, C[par[u]] - dist[u] + 1);
}
if (new_t >= S || new_t == t) break;
t = new_t;
}
}
return make_pair(f, g);
}();
vector<vector<long long>> dist = [&]() -> vector<vector<long long>> {
vector<vector<long long>> dist(n, vector<long long>(n, INF));
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
if (f[u][0][v] != INF) {
dist[u][v] = S;
}
}
}
for (int u = 0; u < n; u++) {
dist[u][u] = 0;
}
for (int w = 0; w < n; w++) {
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
dist[u][v] = min(dist[u][v], dist[u][w] + dist[w][v]);
}
}
}
vector<vector<long long>> true_dist = dist;
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
for (int w = 0; w < n; w++) {
if (f[w][0][v] != INF) {
true_dist[u][v] = min(true_dist[u][v], dist[u][w] + f[w][0][v]);
}
}
}
}
return true_dist;
}();
return [&]() -> vector<long long> {
auto get = [&](int u, int v, long long t) -> long long {
int i = upper_bound(g[u].begin(), g[u].end(), t) - g[u].begin() - 1;
if (f[u][i][v] != INF) {
return f[u][i][v];
}
long long res = INF;
for (int w = 0; w < n; w++) {
if (f[u][i][w] != INF) {
res = min(res, S - t + dist[w][v]);
}
}
return res;
};
vector<long long> res(q);
for (int i = 0; i < q; i++) {
res[i] = get(U[i], V[i], T[i]);
}
return res;
}();
}