Submission #879289

#TimeUsernameProblemLanguageResultExecution timeMemory
879289willychanEscape Route (JOI21_escape_route)C++17
0 / 100
8096 ms150028 KiB
#include "escape_route.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; #define inf 500000000000000000 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) { vector<vector<pair<int,int> >> side(N); for(int i=0; i<M; i++) { side[A[i]].push_back({B[i],i}); side[B[i]].push_back({A[i],i}); } vector<vector<vector<pair<ll,ll> > > > dis(N,vector<vector<pair<ll,ll> >>(N,vector<pair<ll,ll> >(2*M,{inf,inf} ))); for(int e=0; e<M; e++) { int x = A[e]; int y = B[e]; vector<ll> disx(N,inf); vector<ll> disy(N,inf); disx[x]=0; disy[y]=0; vector<bool> reachx(N); vector<bool> reachy(N); ll T = C[e]-L[e]; while(true) { pair<ll,int> cur = {inf,-1}; for(int i=0; i<N; i++) if(!reachx[i]) cur = min(cur, {disx[i],i}); if(cur.first>=inf) break; for(auto g : side[cur.second]) { if(C[g.second]-cur.first<T) continue; if(disx[g.first]>cur.first+L[g.second]) disx[g.first]=cur.first+L[g.second]; } reachx[cur.second]=1; } while(true) { pair<ll,int> cur = {inf,-1}; for(int i=0; i<N; i++) if(!reachy[i]) cur = min(cur, {disy[i],i}); if(cur.first>=inf) break; for(auto g : side[cur.second]) { if(C[g.second]-cur.first-L[g.second]<T) continue; if(disy[g.first]>cur.first+L[g.second]) disy[g.first] = cur.first+L[g.second]; } reachy[cur.second]=1; } for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { dis[i][j][2*e] = {T-disx[i],disx[i]+disy[j]+L[e]}; } } for(int i=0;i<N;i++) reachy[i]=reachx[i]=0; for(int i=0;i<N;i++) disx[i]=disy[i]=inf; disx[x]=0; disy[y]=0; while(true) { pair<ll,int> cur = {inf,-1}; for(int i=0; i<N; i++) if(!reachx[i]) cur = min(cur, {disx[i],i}); if(cur.first>=inf) break; for(auto g : side[cur.second]) { if(C[g.second]-cur.first-L[g.second]<T) continue; if(disx[g.first]>cur.first+L[g.second]) disx[g.first]=cur.first+L[g.second]; } reachx[cur.second]=1; } while(true) { pair<ll,int> cur = {inf,-1}; for(int i=0; i<N; i++) if(!reachy[i]) cur = min(cur, {disy[i],i}); if(cur.first>=inf) break; for(auto g : side[cur.second]) { if(C[g.second]-cur.first<T) continue; if(disy[g.first]>cur.first+L[g.second]) disy[g.first] = cur.first+L[g.second]; } reachy[cur.second]=1; } for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { dis[i][j][2*e+1] = {T-disy[i],disx[j]+disy[i]+L[e]}; } } } for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { sort(dis[i][j].begin(),dis[i][j].end()); for(int e=2*M-2; e>=0; e--) dis[i][j][e].second = min(dis[i][j][e].second,dis[i][j][e+1].second); } } vector<vector<bool> > reach(N,vector<bool>(N,0)); vector<vector<ll> > dis0(N,vector<ll>(N,0)); for(int s=0; s<N; s++) { for(int i=0; i<N; i++) dis0[s][i]=inf; dis0[s][s]=0; while(true) { pair<ll,int> cur = {inf,-1}; for(int i=0; i<N; i++) if(!reach[s][i]) cur = min(cur, {dis0[s][i],i}); if(cur.first>=inf) break; for(auto e : side[cur.second]) { int mind = e.second; if(C[mind]-L[mind]<cur.first) continue; if(dis0[s][e.first]>cur.first+L[mind]) { dis0[s][e.first] = cur.first+L[mind]; } } reach[s][cur.second]=1; } } vector<vector<pair<ll,ll> > > Tdis(N,vector<pair<ll,ll>>(N)); for(int s=0;s<N;s++){ vector<bool> r(N,0); for(int i=0;i<N;i++) Tdis[s][i] = {100,inf}; Tdis[s][s]={0,0}; while(true) { pair<pair<ll,ll>,int> cur = {{100,inf},-1}; for(int i=0;i<N;i++){ if(!r[i]){ cur = min(cur,{Tdis[s][i],i}); } } if(cur.first.first>=100 || cur.first.second>=inf) break; for(int i=0;i<N;i++){ if(dis0[cur.second][i]<S){ if(Tdis[s][i]>make_pair(cur.first.first+1,dis0[cur.second][i])){ Tdis[s][i] = make_pair(cur.first.first+1,dis0[cur.second][i]); } } } r[cur.second]=1; } } vector<ll> ans(Q,inf); /* for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ cout<<i<<" "<<j<<":"<<"("<<Tdis[i][j].first<<","<<Tdis[i][j].second<<")\n"; } }*/ for(int i=0;i<Q;i++){ int u = U[i]; ans[i] = min(ans[i],S-T[i]+Tdis[u][V[i]].second); for(int v=0;v<N;v++){ if(v==u) continue; ll l =-1; ll r = 2*M; while(r-l>1){ ll mid = (r+l)/2; if(dis[u][v][mid].first>=T[i]) r = mid; else l = mid; } if(r>=2*M) continue; if(dis[u][v][r].second+T[i]<S && dis[u][v][r].second>0){ if(v==V[i]){ ans[i] = min(ans[i],dis[u][v][r].second); }else{ ans[i] = min(ans[i],S-T[i]+((Tdis[v][V[i]].first-1)*S)+Tdis[v][V[i]].second); } } } } 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...