Submission #439633

#TimeUsernameProblemLanguageResultExecution timeMemory
439633kig9981Escape Route (JOI21_escape_route)C++17
70 / 100
9019 ms221184 KiB
#include "escape_route.h" #include <bits/stdc++.h> #ifdef NON_SUBMIT #define TEST(n) (n) #define tout cerr #else #define TEST(n) ((void)0) #define tout cin #endif using namespace std; const long long INF=0x7f7f7f7f7f7f7f7fLL; vector<tuple<long long,int,int>> qry[91]; long long CC[91][91], LL[91][91], D[91], PV[91]; int L[92], R[92], P[91]; void dijk(int N, long long S, int r, long long B) { memset(PV,0x7f,sizeof(PV)); memset(D,0x7f,sizeof(D)); D[r]=B; R[0]=1; L[N+1]=N; for(int i=1;i<=N;i++) { L[i]=i-1; R[i]=i+1; } P[r]=r; for(int t=0;t<N;t++) { long long mx=INF; int c=r; for(int j=R[0];j<=N;j=R[j]) if(mx>D[j]) { mx=D[j]; c=j; } L[R[c]]=L[c]; R[L[c]]=R[c]; PV[c]=min(PV[c],PV[P[c]]); for(int j=R[0];j<=N;j=R[j]) if(CC[c][j] && D[j]>(D[c]%S<=CC[c][j]-LL[c][j] ? D[c]:(D[c]+S-1)/S*S)+LL[c][j]) { D[j]=(D[c]%S<=CC[c][j]-LL[c][j] ? D[c]:(D[c]+S-1)/S*S)+LL[c][j]; P[j]=c; if(D[j]<S) PV[j]=CC[c][j]+1-LL[c][j]-D[c]; } } } 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<long long> ret(Q); for(int i=0;i<M;i++) { A[i]++; B[i]++; LL[A[i]][B[i]]=LL[B[i]][A[i]]=L[i]; CC[A[i]][B[i]]=CC[B[i]][A[i]]=C[i]; } for(int i=0;i<Q;i++) qry[++U[i]].emplace_back(T[i],++V[i],i); for(int r=1;r<=N;r++) { long long BB=0; dijk(N,S,r,0); sort(qry[r].rbegin(),qry[r].rend()); while(qry[r].size()) { auto[t,v,i]=qry[r].back(); qry[r].pop_back(); if(t>=BB+PV[v]) dijk(N,S,r,BB=t); ret[i]=D[v]-(D[v]<S ? BB:t); } } return ret; }
#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...