제출 #709763

#제출 시각아이디문제언어결과실행 시간메모리
709763Jarif_RahmanEscape Route (JOI21_escape_route)C++17
20 / 100
522 ms176284 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; 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); vector<vector<tuple<int, ll, ll>>> v(n); 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]}); } vector<vector<ll>> dis2(n); for(int s = 0; s < n; s++){ dis2[s].assign(n, inf); vector<bool> bl(n, 0); priority_queue<pair<ll, int>> pq; 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}); } } } vector<vector<ll>> dis1; vector<ll> sth; ll t = 0; while(1){ ll nxt = inf; sth.pb(t); dis1.pb(vector<ll>(n)); vector<ll> &dis = dis1.back(); dis.assign(n, inf); vector<ll> change(n, inf); vector<bool> bl(n, 0); priority_queue<pair<ll, int>> pq; dis[0] = t; pq.push({0, 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 <= min(dis[x]-1, c)){ dis[x] = dis[nd]+l; change[x] = c-dis[x]+1; pq.push({-dis[x], x}); } } for(ll &x: dis) if(x != inf) x-=t; nxt = min(nxt, *min_element(change.begin(), change.end())); if(nxt == inf) break; t+=nxt; } for(int i = 0; i < q; i++){ int p = (upper_bound(sth.begin(), sth.end(), T[i])-sth.begin())-1; if(dis1[p][V[i]] != inf){ ans[i] = min(ans[i], dis1[p][V[i]]); continue; } for(int j = 0; j < n; j++) if(dis1[p][j] != inf) ans[i] = min(ans[i], S-T[i]+dis2[j][V[i]]); } 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...