제출 #723433

#제출 시각아이디문제언어결과실행 시간메모리
723433piOOEEscape Route (JOI21_escape_route)C++17
0 / 100
1061 ms112000 KiB
#include "escape_route.h" #include <bits/stdc++.h> using namespace std; using ll = long long; vector<ll> calculate_necessary_time(int n, int m, ll S, int q, vector<int> A, vector<int> B, vector<ll> L, vector<ll> C, vector<int> U, vector<int> V, vector<ll> T) { vector<ll> answer(q); vector<vector<int>> queries(n); for (int i = 0; i < q; ++i) { queries[U[i]].push_back(i); } vector<vector<pair<int, int>>> adj(n); for (int i = 0; i < m; ++i) { adj[A[i]].emplace_back(B[i], i); adj[B[i]].emplace_back(A[i], i); } constexpr ll inf = 3e18; auto dijkstra = [&](int source, ll s, bool rev = false) -> vector<ll> { vector<ll> dist(n, rev ? -inf : inf); dist[source] = s; vector<bool> used(n); for (int _ = 0; _ < n; ++_) { int v = -1; for (int i = 0; i < n; ++i) { if (!used[i] && (v == -1 || rev ^ (dist[i] < dist[v]))) { v = i; } } used[v] = true; for (auto [to, i] : adj[v]) { ll d; if (rev) { d = min(dist[v], C[i]) - L[i]; } else { d = L[i] + (dist[v] % S <= C[i] - L[i] ? dist[v] : (dist[v] / S + 1) * S); } if (rev ^ (dist[to] > d)) { dist[to] = d; } } } for (int i = 0; i < n; ++i) { dist[i] = rev ? s - dist[i] : dist[i] - s; } return dist; }; vector from(n, vector<ll>(n)); for (int i = 0; i < n; ++i) { from[i] = dijkstra(i, 0); } vector dto(n, vector<ll>(n)); for (int i = 0; i < n; ++i) { dto[i] = dijkstra(i, S - 1, true); } vector dp(m, vector<ll>(n)); vector<ll> till(m); vector most(n, vector<ll>(n)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i == j) { continue; } ll lo = -1, hi = S; while (lo + 1 < hi) { ll mid = (lo + hi) / 2; if (mid + dijkstra(i, mid)[j] < S) { lo = mid; } else { hi = mid; } } most[i][j] = lo; } } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { ll s = j > 0 ? till[j - 1] + 1 : 0; if (s < S) { vector<ll> d = dijkstra(i, s); dp[j] = d; ll nxt = inf; for (int k = 0; k < m; ++k) { if (d[A[k]] > d[B[k]]) { swap(A[k], B[k]); } if (d[A[k]] + L[k] == d[B[k]] && C[k] - L[k] >= d[A[k]]) { nxt = min(nxt, C[k] - L[k] - d[A[k]]); } } till[j] = s + nxt; } else { dp[j] = vector(n, inf); till[j] = inf; } } for (int j : queries[i]) { ll ans = inf; int to = V[j]; for (int mid = 0; mid < n; ++mid) { ll dist = most[i][mid] < T[j] ? inf : S - 1 - T[j] + 1 + from[mid][to]; ans = min(ans, dist); } int k = lower_bound(till.begin(), till.end(), T[j]) - till.begin(); if (k < m) { ans = min(ans, dp[k][to]); } answer[j] = ans; } } 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...