Submission #879107

#	Time	Username	Problem	Language	Result	Execution time	Memory
879107		willychan	Escape Route (JOI21_escape_route)	C++17	5 / 100	9045 ms	154964 KiB

escape_route

#include "escape_route.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Ba = 90; bitset<Ba> reach[90];
ll dis[90][90];
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) {
	vector<vector<pair<int,int> >> side(N);
	for(int i=0;i<M;i++){
		side[A[i]].push_back({B[i],i});
		side[B[i]].push_back({A[i],i});
	}
	for(int i=0;i<N;i++) reach[i].reset();

	// pre	
		for(int s=0;s<N;s++){
			for(int i=0;i<N;i++) dis[s][i]=1e17;
			dis[s][s]=0;
			priority_queue<pair<ll,int>,vector<pair<ll,int> > ,greater<pair<ll,int> >> pq;
			pq.push({0,s});
			while(pq.size()){
				auto cur = pq.top();
				pq.pop();
				if(dis[s][cur.second]!=cur.first) continue;
				for(auto e : side[cur.second]){
					int mind = e.second;
					if(C[mind]-L[mind]<cur.first) continue;
					if(dis[s][e.first]>cur.first+L[mind]){
						dis[s][e.first] = cur.first+L[mind];
						pq.push({dis[s][e.first],e.first});
					}
				}
			}
		}
	// preend
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++)
			if(dis[i][j]<S) reach[i][j]=1;
	}
	vector<ll>  ans(Q);
	for(int q=0;q<Q;q++){
		vector<ll> qdis(N,1e18);
		qdis[U[q]]=0;
		priority_queue<pair<ll,int>,vector<pair<ll,int> > ,greater<pair<ll,int> >> pq;
		pq.push({0,U[q]});
		while(pq.size()){
			auto cur = pq.top();
			pq.pop();
			if(qdis[cur.second]!=cur.first) continue;
			for(auto e : side[cur.second]){
				int mind = e.second;
				if(C[mind]-L[mind]-T[q]<cur.first) continue;
				if(qdis[e.first]>cur.first+L[mind]){
					qdis[e.first] = cur.first+L[mind];
					pq.push({qdis[e.first],e.first});
				}
			}
		}
		for(int i=0;i<N;i++) if(qdis[i]>S-T[q]) qdis[i]=1e18;
		if(qdis[V[q]]<1e18){
			ans[q] = qdis[V[q]];
			continue;
		}
		ll qans = 1e18;
		queue<pair<int,int> > que;
		bitset<Ba> reachq;
		for(int i=0;i<N;i++){
			if(qdis[i]<1e18 && !reachq[i]) {
				que.push({i,1});
				reachq[i]=1;
			}
		}
		while(que.size()){
			auto cur = que.front();
			que.pop();
			if(dis[cur.first][V[q]]<1e18) qans = min(qans,(S*cur.second)+dis[cur.first][V[q]]);
			for(int j=0;j<N;j++){
				if(reach[cur.first][j] && !reachq[j]){
					que.push({j,cur.second+1});
					reachq[j]=1;
				}
			}
		}
		ans[q] = qans-T[q];
	}



  return ans;
}

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