Submission #439613

#	Time	Username	Problem	Language	Result	Execution time	Memory
439613		kig9981	Escape Route (JOI21_escape_route)	C++17	5 / 100	875 ms	111996 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];
long long D[90][180][90], 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;
	memset(D,0x7f,sizeof(D));
	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;
			D[r][i][r]=x[r][i];
			memset(chk,0,sizeof(chk));
			memset(P,0x7f,sizeof(P));
			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][i][j]) {
					mx=D[r][i][j];
					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][i][j]>(D[r][i][c]%S<=CC[c][j]-LL[c][j] ? D[r][i][c]:(D[r][i][c]+S-1)/S*S)+LL[c][j]) {
					D[r][i][j]=(D[r][i][c]%S<=CC[c][j]-LL[c][j] ? D[r][i][c]:(D[r][i][c]+S-1)/S*S)+LL[c][j];
					if(D[r][i][j]<S) P[j]=CC[c][j]+1-LL[c][j]-D[r][i][c];
				}
			}
			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]][j][V[i]]-(D[U[i]][j][V[i]]<S ? x[U[i]][j]:T[i]));
	}
	return ret;
}

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