Submission #570871

#	Time	Username	Problem	Language	Result	Execution time	Memory
570871		inksamurai	Escape Route (JOI21_escape_route)	C++17	70 / 100	9046 ms	327636 KiB

escape_route

#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(m * m logn)
	const ll lnf=1e18;
	vec(vec(vll)) edp(n,vec(vll)(n,vll(m,lnf)));
	{
		rep(s,n){
			for(auto &[su,sw,sid,slim]:adj[s]){
				vll dp(n,-1);
				dp[su]=slim-sw;
				priority_queue<pii> pq;
				pq.push({dp[su],su});
				while(sz(pq)){
					auto top=pq.top();
					pq.pop();
					ll cosu=top.fi,v=top.se;
					edp[v][v][sid]=(edp[v][v][sid]==lnf?cosu:max(edp[v][v][sid],cosu));
					if(dp[v]!=cosu) continue;
					for(auto &[u,w,nid,lim]:adj[v]){
						ll ncosu=min(cosu-w,lim-w);
						if(ncosu<0 or dp[u]>=ncosu) continue;
						dp[u]=ncosu;
						pq.push({ncosu,u});
					}
				}
			}
		}
	}
	// starting from node (v,time) evaluate minimum path to reach 'k'
	// O(n * m^2 logn)
	//
	// fix me ^
	//
	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
	// O(n^2 * m logn)
	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});
	}
	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;
			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){
				if(ndp[k]!=lnf){
					ans=min(ans,S-qry[v][i].fi+fdp[k][u]);
				}
			}
			if(ndp[u]!=lnf){
				ans=min(ans,ndp[u]);
			}
			ans=min(ans,S-qry[v][i].fi+fdp[v][u]);
			pns[qry[v][i].se]=ans;
		}
	}
	return pns;
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35
• Subtask 5: 0 / 30