Submission #978680

#TimeUsernameProblemLanguageResultExecution timeMemory
978680hotboy2703Escape Route (JOI21_escape_route)C++17
70 / 100
9041 ms352900 KiB
#include "escape_route.h" #include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define BIT(mask,i) (((mask) >> (i))&1LL) #define MASK(i) (1LL << (i)) #define MP make_pair #define pll pair <ll,ll> #define fi first #define se second #define sz(a) (ll((a).size())) namespace{ const ll MAXN = 90; const ll INF = 1e18; ll n,m,s,q; ll c[MAXN+10][MAXN+10],l[MAXN+10][MAXN+10]; ll pre[MAXN+10][MAXN+10]; bool used[MAXN+10]; ll dist[MAXN+10]; ll last_c[MAXN+10]; struct query{ ll u,v,t,id; }; vector <query> all_query; vector <ll> ans; void solve(){ ans.resize(sz(all_query)); sort(all_query.begin(),all_query.end(),[&](query x,query y){return x.u < y.u;}); for (ll i = 1;i <= n;i ++){ for (ll j = 1;j <= n;j ++){dist[j] = INF;used[j] = 0;} dist[i] = 0; for (ll z = 1;z <= n;z ++){ ll u = 0; for (ll j = 1;j <= n;j ++){ if (!used[j] && (!u || dist[j] < dist[u]))u=j; } used[u] = 1; for (ll v = 1;v <= n;v ++){ if (used[v])continue; if (c[u][v] == 0)continue; // if (i == 1 && u == 3)cout<<v<<endl; ll x = dist[u]%s; ll w; if (x + l[u][v] > c[u][v])w = dist[u]+s-x+l[u][v]; else w = dist[u]+l[u][v]; dist[v] = min(dist[v],w); } } for (ll j = 1;j <= n;j ++)pre[j][i] = dist[j]; } // cout<<l[3][4]<<' '<<c[3][4]<<endl; // for (ll i = 1;i <= n;i ++)for (ll j = 1;j <= n;j ++)cout<<pre[i][j]<<" \n"[j==n]; for (ll i = 1,ptr = 0;i <= n;i ++){ vector <query> cur_query; while (ptr<sz(all_query)&&all_query[ptr].u==i){ cur_query.push_back(all_query[ptr]); ptr++; } sort(cur_query.begin(),cur_query.end(),[&](query x,query y){return x.t < y.t;}); // for (auto x:cur_query){ // cout<<x.u<<' '<<x.v<<' '<<x.t<<endl; // } ll ptr_cur=0; ll st = 0; while (1){ // cout<<st<<endl; for (ll j = 1;j <= n;j ++){ dist[j] = INF; used[j] = 0; } dist[i] = st; ll range = INF; for (ll j = 1;j <= n;j ++){ ll u = 0; for (ll k = 1;k <= n;k ++){ if (!used[k]&&(!u || dist[k]<dist[u]))u=k; } used[u] = 1; if (dist[u]==INF)break; if (u != i)range = min(range,last_c[u] - dist[u]); for (ll v = 1;v <= n;v ++){ if (!used[v] && c[u][v]){ if (dist[u] + l[u][v] <= min(dist[v],c[u][v])){ last_c[v] = c[u][v]; dist[v] = dist[u] + l[u][v]; } } } } while (ptr_cur<sz(cur_query)&&cur_query[ptr_cur].t <= st+range){ ll u,v,t,id,res=INF; query x = cur_query[ptr_cur]; tie(u,v,t,id) = tie(x.u,x.v,x.t,x.id); if (dist[v]!=INF)res = dist[v]-st; else{ for (ll k = 1;k <= n;k ++){ if (dist[k] != INF){ res = min(res,pre[v][k]+s-t); } } } ans[id]=res; ptr_cur++; } if (range==INF)break; // cout<<range<<endl; st+=range+1; } } } } 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) { n = N,m = M,s = S,q = Q; for (ll i = 1;i <= n;i ++){ for (ll j = 1;j <= n;j ++){ c[i][j] = 0; l[i][j] = 1; } } for (ll i = 0;i < m;i ++){ ll u,v; u = A[i]+1,v = B[i]+1; c[u][v] = c[v][u] = C[i]; l[u][v] = l[v][u] = L[i]; } for (ll i = 0;i < q;i ++){ all_query.push_back({U[i]+1,V[i]+1,T[i],i}); } solve(); 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...