Submission #439622

#	Time	Username	Problem	Language	Result	Execution time	Memory
439622		kig9981	Escape Route (JOI21_escape_route)	C++17	70 / 100	9075 ms	242748 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<tuple<long long,int,int>> qry[91];
long long CC[91][91], LL[91][91], P[91], D[91];
int L[92], R[92];

long long dijk(int N, long long S, int r, long long B)
{
	long long O=INF;
	memset(P,0x7f,sizeof(P));
	memset(D,0x7f,sizeof(D));
	D[r]=B;
	R[0]=1; L[N+1]=N;
	for(int i=1;i<=N;i++) {
		L[i]=i-1;
		R[i]=i+1;
	}
	for(int t=0;t<N;t++) {
		long long mx=INF;
		int c=r;
		for(int j=R[0];j<=N;j=R[j]) if(mx>D[j]) {
			mx=D[j];
			c=j;
		}
		L[R[c]]=L[c];
		R[L[c]]=R[c];
		O=min(O,P[c]);
		for(int j=R[0];j<=N;j=R[j]) if(CC[c][j] && D[j]>(D[c]%S<=CC[c][j]-LL[c][j] ? D[c]:(D[c]+S-1)/S*S)+LL[c][j]) {
			D[j]=(D[c]%S<=CC[c][j]-LL[c][j] ? D[c]:(D[c]+S-1)/S*S)+LL[c][j];
			if(D[j]<S) P[j]=CC[c][j]+1-LL[c][j]-D[c];
		}
	}
	return O;
}

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(Q);
	for(int i=0;i<M;i++) {
		A[i]++; B[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 i=0;i<Q;i++) qry[++U[i]].emplace_back(T[i],++V[i],i);
	for(int r=1;r<=N;r++) {
		long long BB=0, O=dijk(N,S,r,0);
		sort(qry[r].rbegin(),qry[r].rend());
		while(qry[r].size()) {
			auto[t,v,i]=qry[r].back();
			qry[r].pop_back();
			if(t>=BB+O) O=dijk(N,S,r,BB=t);
			ret[i]=D[v]-(D[v]<S ? BB:t);
		}
	}
	return ret;
}

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