| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 570855 | 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"
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define rng(i,x,n) for(ll i=x;i<n;i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll)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<ll>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
struct E{
ll to,w,i;
ll lim;
E(ll _to,ll _w,ll _i,ll _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){
ll n=N,m=M;
vec(vec(E)) adj(n);
rep(i,m){
adj[A[i]].pb(E(B[i],L[i],i,C[i]));
adj[B[i]].pb(E(A[i],L[i],i,C[i]));
}
// starting from node 'v' what is maximum time such that edge 'e' is reachable.
// O(n^3logn)
const ll lnf=1e18;
vec(vec(vll)) edp(n,vec(vll)(n,vll(m,lnf)));
{
rep(s,n){
rep(i,m){
ll _l=0,_r=S-1;
ll _c=-1;
while(_l<=_r){
ll x=(_l+_r)/2;
bool pok=0;
vll dp(n,lnf);
dp[s]=x;
priority_queue<pii,vec(pii),greater<pii>> pq;
pq.push({x,s});
while(sz(pq)){
auto top=pq.top();
pq.pop();
ll cosu=top.fi,v=top.se;
if(dp[v]!=cosu) continue;
for(auto &[u,w,nid,lim]:adj[v]){
if(u==s) continue;
if(cosu+w<=lim){
if(nid==i){
pok=1;
}
if(dp[u]>cosu+w){
dp[u]=cosu+w;
pq.push({cosu+w,u});
}
}
}
}
if(pok){
_c=x;
_l=x+1;
}else{
_r=x-1;
}
}
edp[s][s][i]=_c;
}
}
}
// print(edp[0][0][2]);
// starting from node (v,time) evaluate minimum path to reach 'k'
// O(n^4 * n logn)
rep(s,n){
// don't forget pencakes !
priority_queue<pii,vec(pii),greater<pii>> pq;
rep(i,m){
if(edp[s][s][i]==lnf) continue;
ll max_time=edp[s][s][i];
pq.push({max_time,s});
while(sz(pq)){
auto top=pq.top();
ll 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){
ll 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,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());
ll 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;
ll u=V[qry[v][i].se];
rep(k,n){
// cout<<ndp[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;
}
signed main(){
_3wX6R40;
vll pns;
int N, M,Q;
long long S;
cin>>N>>M>>S>>Q;
std::vector<int> A(M), B(M);
std::vector<long long> L(M), C(M);
std::vector<int> U(Q), V(Q);
std::vector<long long> T(Q);
for(ll i=0;i<M;i++){
cin>>A[i]>>B[i]>>L[i]>>C[i];
}
for(ll i=0;i<Q;i++){
cin>>U[i]>>V[i]>>T[i];
}
pns=calculate_necessary_time(N,M,S,Q,A,B,L,C,U,V,T);
rep(i,Q){
cout<<pns[i]<<"\n";
}
//
return 0;
}