Submission #570612

#	Time	Username	Problem	Language	Result	Execution time	Memory
570612		inksamurai	Escape Route (JOI21_escape_route)	C++17	0 / 100	9063 ms	2097152 KiB

escape_route

#include <bits/stdc++.h>
#include "escape_route.h"
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<int,int>;
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;
	ll lim;
	E(int _to,int _w,int _lim):to(_to),w(_w),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],C[i]));
		adj[B[i]].pb(E(A[i],L[i],C[i]));
	}
	using tpii=pair<ll,pair<ll,ll>>;
	vec(vec(tpii)) qry(n);
	for(int i=0;i<Q;i++){
		qry[U[i]].pb({i,{V[i],T[i]}});
	}
	const ll lnf=8e18;
	vec(vll) dp;
	auto dijkstra=[&](int s,int t){
		priority_queue<tpii,vec(tpii),greater<tpii>> pq;
		pq.push({t,{s,0}});
		dp=vec(vll)(n+1,vll(n+1,lnf));
		dp[s][0]=t;
		// 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,lim]:adj[v]){
				if(x+w<=lim){
					if(dp[u][day]>now+w){
						dp[u][day]=now+w;
						pq.push({now+w,{u,day}});
					}
				}
			}
		}
	};
	// dijkstra(0,5);
	// rep(u,n){
	// 	rep(j,n){
	// 		cout<<dp[u][j]<<" ";
	// 	}
	// 	print();
	// }
	vll pns(Q,lnf);
	rep(v,n){
		if(!sz(qry[v])) continue;
		for(auto tp:qry[v]){
			dijkstra(v,tp.se.se);
			rep(j,n){
				pns[tp.fi]=min(pns[tp.fi],dp[tp.se.fi][j]-tp.se.se);
			}
		}
	}
	return pns;
}

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