Submission #623650

#TimeUsernameProblemLanguageResultExecution timeMemory
623650valerikkEscape Route (JOI21_escape_route)C++17
35 / 100
9029 ms195692 KiB
#include "escape_route.h" #include <algorithm> #include <cassert> #include <limits> const long long INF = 1e18; 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) { std::vector<long long> answer(Q, INF); std::vector<std::vector<long long>> dists0(N); for (int start = 0; start < N; ++start) { std::vector<std::vector<long long>> l(N, std::vector<long long>(N, -1)); std::vector<std::vector<long long>> c(N, std::vector<long long>(N, -1)); 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]; } std::vector<long long> dist(N, INF); std::vector<bool> used(N, false); dist[start] = 0; for (int it = 0; it < N; ++it) { int u = -1; for (int v = 0; v < N; ++v) { if (!used[v] && (u == -1 || dist[v] < dist[u])) { u = v; } } assert(dist[u] != INF); used[u] = true; long long rem = dist[u] % S; for (int v = 0; v < N; ++v) { if (!used[v] && l[u][v] != -1) { long long new_dist = dist[u] + l[u][v]; if (rem + l[u][v] > c[u][v]) { new_dist = dist[u] + S - rem + l[u][v]; } dist[v] = std::min(dist[v], new_dist); } } } dists0[start] = dist; } for (int start = 0; start < N; ++start) { std::vector<std::vector<long long>> l(N, std::vector<long long>(N, -1)); std::vector<std::vector<long long>> c(N, std::vector<long long>(N, -1)); 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]; } std::vector<long long> stops = {0}; std::vector<std::vector<long long>> dists; while (true) { std::vector<long long> dist(N, INF); std::vector<bool> used(N, false); dist[start] = 0; for (int it = 0; it < N; ++it) { int u = -1; for (int v = 0; v < N; ++v) { if (!used[v] && (u == -1 || dist[v] < dist[u])) { u = v; } } used[u] = true; for (int v = 0; v < N; ++v) { if (l[u][v] != -1 && !used[v]) { dist[v] = std::min(dist[v], dist[u] + l[u][v]); } } } long long stop = INF; for (int u = 0; u < N; ++u) { for (int v = 0; v < N; ++v) { if (l[u][v] != -1) { stop = std::min(stop, std::max(stops.back(), c[u][v] - dist[u] - l[u][v] + 1)); } } } stops.push_back(stop); dists.push_back(dist); for (int u = 0; u < N; ++u) { for (int v = 0; v < N; ++v) { if (l[u][v] != -1 && std::max(stops.back(), c[u][v] - dist[u] - l[u][v] + 1) == stop) { l[u][v] = -1; c[u][v] = -1; } } } if (stop == INF) break; } for (int i = 0; i < Q; ++i) { if (U[i] == start) { int pos = std::upper_bound(begin(stops), end(stops), T[i]) - begin(stops); answer[i] = std::min(answer[i], dists[pos - 1][V[i]]); for (int W = 0; W < N; ++W) { if (dists[pos - 1][W] != INF) { answer[i] = std::min(answer[i], S - T[i] + dists0[W][V[i]]); } } } } } return answer; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...