Submission #623657

#TimeUsernameProblemLanguageResultExecution timeMemory
623657valerikkEscape Route (JOI21_escape_route)C++17
0 / 100
1605 ms112028 KiB
#include "escape_route.h" #include <algorithm> #include <cassert> #include <limits> static const long long INF = 1e18; static const int MAX_N = 61; static const int MAX_M = 1771; 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}; static long long dists[MAX_M][MAX_N]; while (true) { static long long dist[MAX_N]; static bool used[MAX_N]; std::fill(dist, dist + N, INF); std::fill(used, 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; } } if (dist[u] == INF) break; used[u] = true; for (int v = 0; v < N; ++v) { if (!used[v] && l[u][v] != -1) { 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) { long long cur = c[u][v] - dist[u] - l[u][v] + 1; if (cur <= stops.back()) { l[u][v] = -1; c[u][v] = -1; } else { stop = std::min(stop, cur); } } } } std::copy(dist, dist + N, dists[(int) stops.size() - 1]); stops.push_back(stop); for (int u = 0; u < N; ++u) { for (int v = 0; v < N; ++v) { if (l[u][v] != -1 && 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...