제출 #899382

#제출 시각아이디문제언어결과실행 시간메모리
899382boxEscape Route (JOI21_escape_route)C++17
70 / 100
9068 ms198672 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #define bug(x) cerr << "L" << __LINE__ << " | " << #x << " => " << x << endl #else #define bug(x) #define cerr if (0) cerr #endif #define ar array #define sz(v) int(std::size(v)) #define all(v) std::begin(v), std::end(v) using i64 = long long; using vi = vector<int>; using pi = pair<int, int>; vector<i64> calculate_necessary_time(int N, int M, i64 S, int Q, vi A, vi B, vector<i64> L, vector<i64> C, vi U, vi V, vector<i64> T) { const int MAXN = 90; const i64 INF = 1e18; static vi adj[MAXN]; for (int i = 0; i < M; i++) adj[A[i]].push_back(i), adj[B[i]].push_back(i); static i64 dist[MAXN][MAXN], end[MAXN][MAXN]; for (int src = 0; src < N; src++) { { fill(dist[src], dist[src] + N, INF); using X = pair<i64, int>; priority_queue<X, vector<X>, greater<X>> pq; auto ins = [&](int i, i64 d) { if (dist[src][i] > d) pq.push({dist[src][i] = d, i}); }; ins(src, 0); while (sz(pq)) { auto [d, i] = pq.top(); pq.pop(); if (dist[src][i] != d) continue; for (int h : adj[i]) ins(i ^ A[h] ^ B[h], L[h] + (d % S <= C[h] - L[h] ? d : (d / S + 1) * S)); } } { fill(end[src], end[src] + N, -1); using X = pair<i64, int>; priority_queue<X> pq; auto ins = [&](int i, i64 d) { if (end[src][i] < d) pq.push({end[src][i] = d, i}); }; ins(src, S); while (sz(pq)) { auto [d, i] = pq.top(); pq.pop(); if (end[src][i] != d) continue; for (int h : adj[i]) ins(i ^ A[h] ^ B[h], min(C[h], d) - L[h]); } } } vector<i64> ans(Q); static vi at_v[MAXN]; for (int i = 0; i < Q; i++) { i64 x = INF; for (int j = 0; j < N; j++) if (T[i] <= end[j][U[i]]) x = min(x, S - T[i] + dist[j][V[i]]); ans[i] = x; if (dist[U[i]][V[i]] <= S) at_v[U[i]].push_back(i); } for (int src = 0; src < N; src++) { static i64 dist[MAXN]; static bool consider[MAXN]; fill(dist, dist + N, INF); fill(consider, consider + N, false); auto upd = [&](int i, i64 d) { if (dist[i] > d) { dist[i] = d; consider[i] = 1; } }; i64 START = INF; priority_queue<pair<i64, pi>> edges; auto relax = [&]() { while (1) { int i = -1; for (int j = 0; j < N; j++) if (consider[j] && (i == -1 || dist[j] < dist[i])) i = j; if (i == -1) return; consider[i] = 0; for (int h : adj[i]) { int j = i ^ A[h] ^ B[h]; if (dist[j] <= dist[i] + L[h]) continue; if (START + dist[i] + L[h] <= C[h]) upd(j, dist[i] + L[h]); else edges.push({C[h] - dist[i] - L[h], {i, h}}); } } }; upd(src, 0); sort(all(at_v[src]), [&](int i, int j) { return T[i] > T[j]; }); for (int i : at_v[src]) { START = T[i]; while (sz(edges) && edges.top().first >= START) { auto [i, h] = edges.top().second; edges.pop(); int j = i ^ A[h] ^ B[h]; upd(j, dist[i] + L[h]); } relax(); ans[i] = min(ans[i], dist[V[i]]); } } return ans; } #ifdef LOCAL int main() { ios::sync_with_stdio(0); cin.tie(0); int N, M, Q; i64 S; cin >> N >> M >> S >> Q; vi A(M), B(M); vector<i64> L(M), C(M); for (int i = 0; i < M; i++) cin >> A[i] >> B[i] >> L[i] >> C[i]; vi U(Q), V(Q); vector<i64> T(Q); for (int i = 0; i < Q; i++) cin >> U[i] >> V[i] >> T[i]; auto ans = calculate_necessary_time(N, M, S, Q, A, B, L, C, U, V, T); assert(sz(ans) == Q); for (int i = 0; i < Q; i++) cout << ans[i] << '\n'; } #endif
#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...