Submission #1213759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213759		salmon	Escape Route (JOI21_escape_route)	C++20	100 / 100	2396 ms	670736 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;

namespace{
	const long long int inf = 1.1e18;
}		

long long int d[100][10100][100];

vector<long long> calculate_necessary_time(
    int N, int M, long long S, int Q, vector<int> A, vector<int> B,
    vector<long long> L, vector<long long> C, vector<int> U,
    vector<int> V, vector<long long> T) {

	vector<int> adjlst[100];
	vector<vector<long long int>> ds[100];
	vector<long long int> turns[100];
	vector<long long int> turns1[100];
	bool used[100];
	int dit[100];

	pair<long long int, long long int> adjmat[100][100];
	
	for(int i = 0; i < M; i++){
		A.push_back(B[i]);
		B.push_back(A[i]);
		L.push_back(L[i]);
		C.push_back(C[i]);
	}
	
	for(int i = 0; i < M; i++){
		adjlst[A[i]].push_back(i);
		adjlst[B[i]].push_back(i + M);
	}
	
	for(int i = 0; i < N; i++){
		for(int j : adjlst[i]) turns[i].push_back(C[j] - L[j]);
		
		sort(turns[i].begin(),turns[i].end(), greater<long long int>());
		turns[i].resize(unique(turns[i].begin(),turns[i].end()) - turns[i].begin() );
	}
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < turns[i].size(); j++){
			vector<long long int> temp = {};
			
			for(int j = 0; j < N; j++){
				temp.push_back(inf);
				used[j] = false;
			}
			
			ds[i].push_back(temp);
			
			ds[i][j][i] = turns[i][j];
			
			for(int k = 0; k < N; k++){
				pair<long long int, int> ii = {inf,-1};
				
				for(int l = 0; l < N; l++) if(!used[l]) ii = min(ii,{ds[i][j][l],l });
				
				if(ii.first == inf) break;
				
				used[ii.second] = true;
				
				int it = ii.second;
				
				for(int l : adjlst[it]){
					if(ii.first + L[l] <= C[l]) ds[i][j][B[l]] = min(ds[i][j][B[l]], ii.first + L[l]);
				}
			}
		}
	}
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			adjmat[i][j] = {inf,inf};
		}
	}
	
	for(int i = 0; i < N; i++){
		long long int incre = turns[i][0];
		long long int diff = inf;
		//it 1
		
		turns1[i].push_back(incre);
		
		for(int j = 0; j < N; j++){
			dit[j] = 0;
			d[i][0][j] = ds[i][0][j];
		}
		
		for(int j = 0; j < N; j++){
			if(d[i][0][j] == inf) continue;
			while(dit[j] != turns[j].size() && turns[j][dit[j]] >= d[i][0][j]){
				dit[j]++;
			}
			if(dit[j] == turns[j].size()) continue;
			diff = min(diff,d[i][0][j] - turns[j][dit[j]] );
		}
		
		incre = incre - diff;
		
		//it
		
		for(int l = 1; l < M * 2 + 5; l++){
			if(incre < 0) break;
			
			turns1[i].push_back(incre);
			
			for(int j = 0; j < N; j++) d[i][l][j] = min(inf,d[i][l - 1][j] +  d[i][l - 1][j] * (inf == d[i][l - 1][j]) - diff);
			
			for(int j = 0; j < N; j++){
				if(dit[j] == turns[j].size()) continue;
				if(d[i][l - 1][j] - turns[j][dit[j]] != diff) continue;
				for(int k = 0; k < N; k++){
					d[i][l][k] = min(d[i][l][k], ds[j][dit[j]][k]);
				}
				dit[j]++;
			}
			
			diff = inf;
			
			for(int j = 0; j < N; j++){
				if(d[i][l][j] == inf) continue;
				while(dit[j] != turns[j].size() && turns[j][dit[j]] >= d[i][l][j]){
					dit[j]++;
				}
				if(dit[j] == turns[j].size()) continue;
				diff = min(diff,d[i][l][j] - turns[j][dit[j]] );
			}
			
			if(incre - diff < 0) break;
			
			incre = incre - diff;
				
		}
		
		if(incre < 0) incre += diff;
		
		int it = turns1[i].size() - 1;
		
		for(int j = 0; j < N; j++){
			if(d[i][it][j] == inf) continue;
			adjmat[i][j] = {1,d[i][it][j] - incre};
		}
	}
	
	
	for(int k = 0; k < N; k++){
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				adjmat[i][j] = min(adjmat[i][j],{adjmat[i][k].first + adjmat[k][j].first, adjmat[k][j].second });
			}
		}
	}
	
	/*printf("\n");
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			printf("%lld ",adjmat[i][j].first);
		}
		printf("\n");
	}
	printf("\n");*/
	
	vector<long long> ans;
	
	for(int i = 0; i < Q; i++){
		int u = U[i];
		int v = V[i];
		long long int h = T[i];
		
		int it = upper_bound(turns1[u].begin(),turns1[u].end(),h,greater<long long>()) - turns1[u].begin() - 1;
		
		if(it != -1 && d[u][it][v] != inf){
			ans.push_back(d[u][it][v] - d[u][it][u]);
			//printf("yes %lld\n",ans.back());
		}
		else{
			if(it == -1){
				ans.push_back(adjmat[u][v].first * S + adjmat[u][v].second - h);//printf("2 %lld\n",ans.back());	
				continue;
			}
			
			pair<long long int,long long int> ii = {inf,inf};
			
			for(int j = 0; j < N; j++){
				if(d[u][it][j] != inf) ii = min(adjmat[j][v],ii);
			}
			
			ans.push_back(ii.first * S + ii.second - h);
					//printf("%lld\n",ans.back());	
		}
		
	}
	
	return ans;
	
}

/*
int main(){
	int N;
	int M;
	long long int S;
	int Q;
	
	vector<int> A;
	vector<int> B;
	vector<long long int> L;
	vector<long long int> C;
	
	vector<int> U;
	vector<int> V;
	vector<long long int> T;
	
	scanf(" %d",&N);
	scanf(" %d",&M);
	scanf(" %lld",&S);
	scanf(" %d",&Q);
	
	for(int i = 0; i < M; i++){
		int h,h1;
		long long int h2,h3;
		
		scanf(" %d",&h);
		scanf(" %d",&h1);
		scanf(" %lld",&h2);
		scanf(" %lld",&h3);
		
		A.push_back(h);
		B.push_back(h1);
		L.push_back(h2);
		C.push_back(h3);
	}
	
	for(int i = 0; i < Q; i++){
		int h1,h2;
		long long int h3;
		
		scanf(" %d",&h1);
		scanf(" %d",&h2);
		scanf(" %lld",&h3);
		
		U.push_back(h1);
		V.push_back(h2);
		T.push_back(h3);
	}
	printf("yes\n");
	vector<long long int> ans = calculate_necessary_time(N,M,S,Q,A,B,L,C,U,V,T);
	
	for(long long int j : ans) printf("%lld\n",j);
}
*/
													

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