oj.uz

Submission #439614

# Submission time Handle Problem Language Result Execution time Memory
439614 2021-06-30T10:57:12 Z kig9981 Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 238768 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<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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 65240 KB Output is correct
2 Correct 48 ms 65148 KB Output is correct
3 Correct 111 ms 65220 KB Output is correct
4 Correct 28 ms 65228 KB Output is correct
5 Correct 30 ms 65204 KB Output is correct
6 Correct 31 ms 65240 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 886 ms 119488 KB Output is correct
2 Correct 915 ms 185960 KB Output is correct
3 Correct 521 ms 155424 KB Output is correct
4 Correct 1041 ms 195572 KB Output is correct
5 Correct 1065 ms 195568 KB Output is correct
6 Correct 32 ms 65220 KB Output is correct
7 Correct 557 ms 155156 KB Output is correct
8 Correct 471 ms 190596 KB Output is correct
9 Correct 849 ms 152540 KB Output is correct
10 Correct 1098 ms 189608 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 65240 KB Output is correct
2 Correct 48 ms 65148 KB Output is correct
3 Correct 111 ms 65220 KB Output is correct
4 Correct 28 ms 65228 KB Output is correct
5 Correct 30 ms 65204 KB Output is correct
6 Correct 31 ms 65240 KB Output is correct
7 Correct 886 ms 119488 KB Output is correct
8 Correct 915 ms 185960 KB Output is correct
9 Correct 521 ms 155424 KB Output is correct
10 Correct 1041 ms 195572 KB Output is correct
11 Correct 1065 ms 195568 KB Output is correct
12 Correct 32 ms 65220 KB Output is correct
13 Correct 557 ms 155156 KB Output is correct
14 Correct 471 ms 190596 KB Output is correct
15 Correct 849 ms 152540 KB Output is correct
16 Correct 1098 ms 189608 KB Output is correct
17 Correct 1048 ms 162668 KB Output is correct
18 Correct 1138 ms 162468 KB Output is correct
19 Correct 1154 ms 184292 KB Output is correct
20 Correct 661 ms 155188 KB Output is correct
21 Correct 1331 ms 192928 KB Output is correct
22 Correct 1282 ms 192748 KB Output is correct
23 Correct 613 ms 155168 KB Output is correct
24 Correct 529 ms 191712 KB Output is correct
25 Correct 957 ms 154980 KB Output is correct
26 Correct 1279 ms 193332 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 65240 KB Output is correct
2 Correct 48 ms 65148 KB Output is correct
3 Correct 111 ms 65220 KB Output is correct
4 Correct 28 ms 65228 KB Output is correct
5 Correct 30 ms 65204 KB Output is correct
6 Correct 31 ms 65240 KB Output is correct
7 Correct 886 ms 119488 KB Output is correct
8 Correct 915 ms 185960 KB Output is correct
9 Correct 521 ms 155424 KB Output is correct
10 Correct 1041 ms 195572 KB Output is correct
11 Correct 1065 ms 195568 KB Output is correct
12 Correct 32 ms 65220 KB Output is correct
13 Correct 557 ms 155156 KB Output is correct
14 Correct 471 ms 190596 KB Output is correct
15 Correct 849 ms 152540 KB Output is correct
16 Correct 1098 ms 189608 KB Output is correct
17 Correct 1048 ms 162668 KB Output is correct
18 Correct 1138 ms 162468 KB Output is correct
19 Correct 1154 ms 184292 KB Output is correct
20 Correct 661 ms 155188 KB Output is correct
21 Correct 1331 ms 192928 KB Output is correct
22 Correct 1282 ms 192748 KB Output is correct
23 Correct 613 ms 155168 KB Output is correct
24 Correct 529 ms 191712 KB Output is correct
25 Correct 957 ms 154980 KB Output is correct
26 Correct 1279 ms 193332 KB Output is correct
27 Correct 3375 ms 201052 KB Output is correct
28 Correct 3782 ms 204404 KB Output is correct
29 Correct 4148 ms 229396 KB Output is correct
30 Correct 879 ms 162724 KB Output is correct
31 Correct 4421 ms 236640 KB Output is correct
32 Correct 4482 ms 238768 KB Output is correct
33 Correct 550 ms 194384 KB Output is correct
34 Correct 3277 ms 190280 KB Output is correct
35 Correct 4419 ms 237708 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 65240 KB Output is correct
2 Correct 48 ms 65148 KB Output is correct
3 Correct 111 ms 65220 KB Output is correct
4 Correct 28 ms 65228 KB Output is correct
5 Correct 30 ms 65204 KB Output is correct
6 Correct 31 ms 65240 KB Output is correct
7 Correct 886 ms 119488 KB Output is correct
8 Correct 915 ms 185960 KB Output is correct
9 Correct 521 ms 155424 KB Output is correct
10 Correct 1041 ms 195572 KB Output is correct
11 Correct 1065 ms 195568 KB Output is correct
12 Correct 32 ms 65220 KB Output is correct
13 Correct 557 ms 155156 KB Output is correct
14 Correct 471 ms 190596 KB Output is correct
15 Correct 849 ms 152540 KB Output is correct
16 Correct 1098 ms 189608 KB Output is correct
17 Correct 1048 ms 162668 KB Output is correct
18 Correct 1138 ms 162468 KB Output is correct
19 Correct 1154 ms 184292 KB Output is correct
20 Correct 661 ms 155188 KB Output is correct
21 Correct 1331 ms 192928 KB Output is correct
22 Correct 1282 ms 192748 KB Output is correct
23 Correct 613 ms 155168 KB Output is correct
24 Correct 529 ms 191712 KB Output is correct
25 Correct 957 ms 154980 KB Output is correct
26 Correct 1279 ms 193332 KB Output is correct
27 Correct 3375 ms 201052 KB Output is correct
28 Correct 3782 ms 204404 KB Output is correct
29 Correct 4148 ms 229396 KB Output is correct
30 Correct 879 ms 162724 KB Output is correct
31 Correct 4421 ms 236640 KB Output is correct
32 Correct 4482 ms 238768 KB Output is correct
33 Correct 550 ms 194384 KB Output is correct
34 Correct 3277 ms 190280 KB Output is correct
35 Correct 4419 ms 237708 KB Output is correct
36 Execution timed out 9034 ms 194396 KB Time limit exceeded
37 Halted 0 ms 0 KB -