oj.uz

Submission #439622

# Submission time Handle Problem Language Result Execution time Memory
439622 2021-06-30T11:31:20 Z kig9981 Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 242748 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 64964 KB Output is correct
2 Correct 39 ms 64944 KB Output is correct
3 Correct 47 ms 65004 KB Output is correct
4 Correct 44 ms 64988 KB Output is correct
5 Correct 36 ms 64964 KB Output is correct
6 Correct 37 ms 64932 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 793 ms 153040 KB Output is correct
2 Correct 883 ms 218636 KB Output is correct
3 Correct 869 ms 200132 KB Output is correct
4 Correct 916 ms 227584 KB Output is correct
5 Correct 911 ms 226916 KB Output is correct
6 Correct 36 ms 64932 KB Output is correct
7 Correct 850 ms 199272 KB Output is correct
8 Correct 953 ms 239000 KB Output is correct
9 Correct 802 ms 186940 KB Output is correct
10 Correct 899 ms 226828 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 64964 KB Output is correct
2 Correct 39 ms 64944 KB Output is correct
3 Correct 47 ms 65004 KB Output is correct
4 Correct 44 ms 64988 KB Output is correct
5 Correct 36 ms 64964 KB Output is correct
6 Correct 37 ms 64932 KB Output is correct
7 Correct 793 ms 153040 KB Output is correct
8 Correct 883 ms 218636 KB Output is correct
9 Correct 869 ms 200132 KB Output is correct
10 Correct 916 ms 227584 KB Output is correct
11 Correct 911 ms 226916 KB Output is correct
12 Correct 36 ms 64932 KB Output is correct
13 Correct 850 ms 199272 KB Output is correct
14 Correct 953 ms 239000 KB Output is correct
15 Correct 802 ms 186940 KB Output is correct
16 Correct 899 ms 226828 KB Output is correct
17 Correct 998 ms 198156 KB Output is correct
18 Correct 1037 ms 197048 KB Output is correct
19 Correct 1118 ms 221624 KB Output is correct
20 Correct 828 ms 201464 KB Output is correct
21 Correct 1160 ms 228804 KB Output is correct
22 Correct 1152 ms 229384 KB Output is correct
23 Correct 819 ms 201220 KB Output is correct
24 Correct 913 ms 242748 KB Output is correct
25 Correct 978 ms 191428 KB Output is correct
26 Correct 1187 ms 228700 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 64964 KB Output is correct
2 Correct 39 ms 64944 KB Output is correct
3 Correct 47 ms 65004 KB Output is correct
4 Correct 44 ms 64988 KB Output is correct
5 Correct 36 ms 64964 KB Output is correct
6 Correct 37 ms 64932 KB Output is correct
7 Correct 793 ms 153040 KB Output is correct
8 Correct 883 ms 218636 KB Output is correct
9 Correct 869 ms 200132 KB Output is correct
10 Correct 916 ms 227584 KB Output is correct
11 Correct 911 ms 226916 KB Output is correct
12 Correct 36 ms 64932 KB Output is correct
13 Correct 850 ms 199272 KB Output is correct
14 Correct 953 ms 239000 KB Output is correct
15 Correct 802 ms 186940 KB Output is correct
16 Correct 899 ms 226828 KB Output is correct
17 Correct 998 ms 198156 KB Output is correct
18 Correct 1037 ms 197048 KB Output is correct
19 Correct 1118 ms 221624 KB Output is correct
20 Correct 828 ms 201464 KB Output is correct
21 Correct 1160 ms 228804 KB Output is correct
22 Correct 1152 ms 229384 KB Output is correct
23 Correct 819 ms 201220 KB Output is correct
24 Correct 913 ms 242748 KB Output is correct
25 Correct 978 ms 191428 KB Output is correct
26 Correct 1187 ms 228700 KB Output is correct
27 Correct 2531 ms 199888 KB Output is correct
28 Correct 2638 ms 200296 KB Output is correct
29 Correct 2772 ms 221832 KB Output is correct
30 Correct 991 ms 202056 KB Output is correct
31 Correct 3018 ms 229388 KB Output is correct
32 Correct 3067 ms 232088 KB Output is correct
33 Correct 912 ms 240428 KB Output is correct
34 Correct 2293 ms 191632 KB Output is correct
35 Correct 2986 ms 229136 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 64964 KB Output is correct
2 Correct 39 ms 64944 KB Output is correct
3 Correct 47 ms 65004 KB Output is correct
4 Correct 44 ms 64988 KB Output is correct
5 Correct 36 ms 64964 KB Output is correct
6 Correct 37 ms 64932 KB Output is correct
7 Correct 793 ms 153040 KB Output is correct
8 Correct 883 ms 218636 KB Output is correct
9 Correct 869 ms 200132 KB Output is correct
10 Correct 916 ms 227584 KB Output is correct
11 Correct 911 ms 226916 KB Output is correct
12 Correct 36 ms 64932 KB Output is correct
13 Correct 850 ms 199272 KB Output is correct
14 Correct 953 ms 239000 KB Output is correct
15 Correct 802 ms 186940 KB Output is correct
16 Correct 899 ms 226828 KB Output is correct
17 Correct 998 ms 198156 KB Output is correct
18 Correct 1037 ms 197048 KB Output is correct
19 Correct 1118 ms 221624 KB Output is correct
20 Correct 828 ms 201464 KB Output is correct
21 Correct 1160 ms 228804 KB Output is correct
22 Correct 1152 ms 229384 KB Output is correct
23 Correct 819 ms 201220 KB Output is correct
24 Correct 913 ms 242748 KB Output is correct
25 Correct 978 ms 191428 KB Output is correct
26 Correct 1187 ms 228700 KB Output is correct
27 Correct 2531 ms 199888 KB Output is correct
28 Correct 2638 ms 200296 KB Output is correct
29 Correct 2772 ms 221832 KB Output is correct
30 Correct 991 ms 202056 KB Output is correct
31 Correct 3018 ms 229388 KB Output is correct
32 Correct 3067 ms 232088 KB Output is correct
33 Correct 912 ms 240428 KB Output is correct
34 Correct 2293 ms 191632 KB Output is correct
35 Correct 2986 ms 229136 KB Output is correct
36 Execution timed out 9075 ms 168268 KB Time limit exceeded
37 Halted 0 ms 0 KB -