| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 570784 | inksamurai | Escape Route (JOI21_escape_route) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "escape_route.h"
#define int long long
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3wX6R40 ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<ll,ll>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
struct E{
int to,w,i;
ll lim;
E(int _to,int _w,int _i,int _lim):to(_to),w(_w),i(_i),lim(_lim){}
};
using vll=std::vector<long long>;
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){
int n=N,m=M;
vec(vec(E)) adj(n);
rep(i,m){
adj[A[i]].pb(E(B[i],L[i],2*i,C[i]));
adj[B[i]].pb(E(A[i],L[i],2*i+1,C[i]));
}
// starting from node 'v' what is maximum time such that edge 'e' is reachable.
// O(n^3logn)
const ll lnf=8e18;
vec(vec(vll)) edp(n,vec(vll)(n,vll(2*m+1,lnf)));
{
priority_queue<pair<ll,pair<int,int>>,vec(pair<ll,pair<int,int>>),greater<pair<ll,pair<int,int>>>> pq;
rep(s,n){
pq.push({0,{-1,s}});
while(sz(pq)){
auto top=pq.top();
int v=top.se.se;
int id=top.se.fi;
ll cosu=top.fi;
pq.pop();
if(id!=-1 and edp[s][s][id]!=cosu) continue;
for(auto &[u,w,nid,lim]:adj[v]){
ll ncosu=cosu+w;
if(ncosu>lim) continue;
if(edp[s][s][nid]>ncosu){
edp[s][s][nid]=ncosu;
pq.push({ncosu,{nid,u}});
}
}
}
rep(i,2*m){
if(edp[s][s][i]==lnf) continue;
// if(s==0) print(edp[s][s][i]);
edp[s][s][i]=C[i/2]-edp[s][s][i];
}
}
}
// starting from node (v,time) evaluate minimum path to reach 'k'
// O(n^4 * n logn)
rep(s,n){
// don't forget pencakes !
using P=pair<ll,int>;
priority_queue<P,vec(P),greater<P>> pq;
rep(i,2*m){
if(edp[s][s][i]==-1) continue;
ll max_time=edp[s][s][i];
pq.push({max_time,s});
while(sz(pq)){
auto top=pq.top();
int v=top.se;
ll cosu=top.fi;
pq.pop();
if(edp[s][v][i]!=cosu) continue;
for(auto &[u,w,nid,lim]:adj[v]){
if(u==s) continue;
if(cosu+w<=lim){
if(edp[s][u][i]>cosu+w){
edp[s][u][i]=cosu+w;
pq.push({cosu+w,u});
}
}
}
}
}
}
// evaluate dp(v,u) minimum time to reach 'u' from 'v'
// with starting with cost 0
vec(vll) fdp(n,vll(n,lnf));
{
using tpii=pair<ll,pair<ll,ll>>;
priority_queue<tpii,vec(tpii),greater<tpii>> pq;
vec(vll) dp;
rep(s,n){
pq.push({0,{s,0}});
dp=vec(vll)(n,vll(n+1,lnf));
dp[s][0]=0;
// v,number of days
while(sz(pq)){
auto top=pq.top();
ll now=top.fi,v=top.se.fi,day=top.se.se;
pq.pop();
if(dp[v][day]!=now) continue;
ll x=now%S;
if(day+1<=n){
if(dp[v][day+1]>now+(S-x)){
dp[v][day+1]=now+S-x;
pq.push({now+S-x,{v,day+1}});
}
}
for(auto &[u,w,id,lim]:adj[v]){
if(x+w<=lim){
if(dp[u][day]>now+w){
dp[u][day]=now+w;
pq.push({now+w,{u,day}});
}
}
}
}
rep(u,n){
if(s==u) continue;
ll mi=lnf;
rep(i,n+1) mi=min(mi,dp[u][i]);
fdp[s][u]=mi;
}
}
}
// answer each query from fixed v
vec(vec(pair<ll,ll>)) qry(n);
rep(i,Q){
int u=U[i],t=T[i];
qry[u].pb({t,i});
}
// print(edp[0][2][1]);
vll pns(Q);
rep(v,n){
sort(qry[v].rbegin(),qry[v].rend());
vec(pii) rbts;
rep(i,2*m){
if(edp[v][v][i]==lnf) continue;
// if(v==0) print(edgep[v][v][i]);
rbts.pb({edp[v][v][i],i});
}
sort(rbts.begin(),rbts.end());
int r=sz(rbts)-1;
vll ndp(n,lnf);
rep(i,sz(qry[v])){
while(r>=0 and rbts[r].fi>=qry[v][i].fi){
rep(k,n){
if(edp[v][k][rbts[r].se]!=lnf){
ndp[k]=min(ndp[k],edp[v][k][rbts[r].se]-edp[v][v][rbts[r].se]);
}
}
r-=1;
}
ll ans=lnf;
int u=V[qry[v][i].se];
rep(k,n){
if(ndp[k]!=lnf){
// if(v==1) print(k,ndp[k],S-qry[v][i].fi+fdp[k][u]);
ans=min(ans,S-qry[v][i].fi+fdp[k][u]);
}
}
if(ndp[u]!=lnf){
ans=min(ans,ndp[u]);
}
// if(v==0) print(S-qry[v][i].se+fdp[v][u]);
ans=min(ans,S-qry[v][i].fi+fdp[v][u]);
pns[qry[v][i].se]=ans;
}
}
return pns;
}