제출 #709830

#제출 시각아이디문제언어결과실행 시간메모리
709830Jarif_RahmanEscape Route (JOI21_escape_route)C++17
35 / 100
9015 ms147580 KiB
#include "escape_route.h" #include <bits/stdc++.h> #define pb push_back #define f first #define sc second using namespace std; typedef long long int ll; typedef string str; const ll inf = 5e17; const int N = 90; vector<tuple<int, ll, ll>> v[N]; bitset<N> bl; priority_queue<pair<ll, int>> pq; ll dis2[N][N]; ll dis[N]; vector<int> Q[N]; 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> ans(q, inf); for(int i = 0; i < m; i++){ v[A[i]].pb({B[i], L[i], C[i]}); v[B[i]].pb({A[i], L[i], C[i]}); } for(int i = 0; i < q; i++){ Q[U[i]].pb(i); } for(int i = 0; i < n; i++){ sort(Q[i].begin(), Q[i].end(), [&](int a, int b){ return T[a] < T[b]; }); } for(int s = 0; s < n; s++){ fill(dis2[s], dis2[s]+n, inf); for(int i = 0; i < n; i++) bl[i] = 0; dis2[s][s] = 0; pq.push({0, s}); while(!pq.empty()){ int nd = pq.top().sc; pq.pop(); if(bl[nd]) continue; bl[nd] = 1; for(auto [x, l, c]: v[nd]) if((dis2[s][nd]%S+l<=c ? dis2[s][nd]+l:((dis2[s][nd]+S-1)/S)*S+l) < dis2[s][x]){ dis2[s][x] = (dis2[s][nd]%S+l<=c ? dis2[s][nd]+l:((dis2[s][nd]+S-1)/S)*S+l); pq.push({-dis2[s][x], x}); } } } bl.reset(); bl.flip(); for(int s = 0; s < n; s++){ ll t = S; priority_queue<tuple<ll, int, ll>> sth; sth.push({S, s, 0}); fill(dis, dis+n, inf); while(!Q[s].empty()){ while(!sth.empty() && get<0>(sth.top()) == t){ auto [ig, x, w] = sth.top(); sth.pop(); dis[x] = min(dis[x], w); pq.push({-dis[x], x}); bl[x] = 0; } while(!pq.empty()){ int nd = pq.top().sc; pq.pop(); if(bl[nd]) continue; bl[nd] = 1; for(auto [x, l, c]: v[nd]) if(dis[nd]+l < dis[x]){ if(dis[nd]+l <= c-t){ dis[x] = dis[nd]+l; pq.push({-dis[x], x}); bl[x] = 0; } else{ sth.push({c-dis[nd]-l, x, dis[nd]+l}); } } } if(!sth.empty()) t = get<0>(sth.top()); else t = -inf; while(!Q[s].empty() && T[Q[s].back()] > t){ int i = Q[s].back(); Q[s].pop_back(); if(dis[V[i]] != inf){ ans[i] = min(ans[i], dis[V[i]]); continue; } for(int j = 0; j < n; j++) if(dis[j] != inf) ans[i] = min(ans[i], S-T[i]+dis2[j][V[i]]); } if(t < 0) break; } } return ans; }
#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...