Submission #439614

#	Time	Username	Problem	Language	Result	Execution time	Memory
439614		kig9981	Escape Route (JOI21_escape_route)	C++17	70 / 100	9034 ms	238768 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

const long long INF=0x7f7f7f7f7f7f7f7fLL;
vector<long long> x[90], D[90][90];
long long CC[90][90], LL[90][90], P[90];
bool chk[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<long long> ret;
	for(int i=0;i<M;i++) {
		LL[A[i]][B[i]]=LL[B[i]][A[i]]=L[i];
		CC[A[i]][B[i]]=CC[B[i]][A[i]]=C[i];
	}
	for(int r=0;r<N;r++) {
		x[r].push_back(0);
		for(int i=0;;i++) {
			long long O=INF;
			memset(chk,0,sizeof(chk));
			memset(P,0x7f,sizeof(P));
			for(int j=0;j<N;j++) D[r][j].push_back(INF);
			D[r][r][i]=x[r][i];
			for(int t=0;t<N;t++) {
				long long mx=INF;
				int c=r;
				for(int j=0;j<N;j++) if(!chk[j] && mx>D[r][j][i]) {
					mx=D[r][j][i];
					c=j;
				}
				chk[c]=true;
				O=min(O,P[c]);
				for(int j=0;j<N;j++) if(!chk[j] && CC[c][j] && D[r][j][i]>(D[r][c][i]%S<=CC[c][j]-LL[c][j] ? D[r][c][i]:(D[r][c][i]+S-1)/S*S)+LL[c][j]) {
					D[r][j][i]=(D[r][c][i]%S<=CC[c][j]-LL[c][j] ? D[r][c][i]:(D[r][c][i]+S-1)/S*S)+LL[c][j];
					if(D[r][j][i]<S) P[j]=CC[c][j]+1-LL[c][j]-D[r][c][i];
				}
			}
			if(O==INF) break;
			x[r].push_back(x[r].back()+O);
		}
	}
	for(int i=0;i<Q;i++) {
		int j=upper_bound(x[U[i]].begin(),x[U[i]].end(),T[i])-x[U[i]].begin()-1;
		ret.push_back(D[U[i]][V[i]][j]-(D[U[i]][V[i]][j]<S ? x[U[i]][j]:T[i]));
	}
	return ret;
}

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