Submission #1026899

#TimeUsernameProblemLanguageResultExecution timeMemory
1026899AdamGSEscape Route (JOI21_escape_route)C++17
5 / 100
9071 ms155316 KiB
#include "escape_route.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const ll INF=1e18+7; const int LIM=107; pair<ll,ll>T[LIM][LIM]; vector<ll>P[LIM]; ll n, S, q; void calc1() { rep(i, n) { rep(j, n) P[i].pb(INF); vector<ll>odw(n); P[i][i]=0; while(true) { pair<ll,ll>mi={INF, INF}; rep(j, n) if(!odw[j]) mi=min(mi, {P[i][j], j}); if(mi.st==INF) break; ll p=mi.nd; odw[p]=1; rep(j, n) if(!odw[j] && T[p][j].nd!=-1) { ll a=mi.st/S, b=mi.st%S; if(b<=T[p][j].nd-T[p][j].st) P[i][j]=min(P[i][j], mi.st+T[p][j].st); else P[i][j]=min(P[i][j], (a+1)*S+T[p][j].st); } } } } vector<ll>calc2(ll a, ll b) { vector<ll>odl(n, INF), odw(n); odl[a]=b; while(true) { pair<ll,ll>mi={INF, INF}; rep(i, n) if(!odw[i]) mi=min(mi, {odl[i], i}); if(mi.st==INF) break; ll p=mi.nd; odw[p]=1; rep(i, n) if(!odw[i] && T[p][i].nd!=-1) { if(mi.st<=T[p][i].nd-T[p][i].st) odl[i]=min(odl[i], mi.st+T[p][i].st); } } return odl; } 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) { n=_n; S=_S; q=_q; rep(i, n) rep(j, n) T[i][j]={0, -1}; rep(i, _m) T[_A[i]][_B[i]]=T[_B[i]][_A[i]]={_L[i], _C[i]}; calc1(); vector<ll>ans(q, INF); rep(i, q) { ll a=_U[i], b=_V[i], c=_T[i]; vector<ll>A=calc2(a, c); if(A[b]<INF) { ans[i]=A[b]-c; continue; } rep(j, n) if(A[j]<INF) ans[i]=min(ans[i], S+P[j][b]-c); } 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...