oj.uz

Submission #600372

# Submission time Handle Problem Language Result Execution time Memory
600372 2022-07-20T19:20:59 Z idiot123 Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1236048 KB 
#include<bits/stdc++.h>
#include "dungeons.h"

using namespace std;

//we will use powers of 4 to decide what is the best jump
const int MAX_BIT = 13;
//jumps are base 4 to save memory
const int MAX_JUMP = 12;
const long long INF = 1e18;
vector<array<array<int, MAX_JUMP>, MAX_BIT>> jump;
vector<array<array<long long, MAX_JUMP>, MAX_BIT>> maxVal;
vector<array<array<long long, MAX_JUMP>, MAX_BIT>> sum;
int N;

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
	N = n;
	vector<bool> vis(n+1, false);
	jump.resize(n+1);
	maxVal.resize(n+1);
	sum.resize(n+1);
	for(int i = 0; i < n; i++){
		for(int bit = 0; bit < MAX_BIT; bit++){
			if((1<<(2*bit)) >= s[i]){
				jump[i][bit][0] = w[i];
				maxVal[i][bit][0] = INF;
				sum[i][bit][0] = s[i];
			}else{
				jump[i][bit][0] = l[i];
				maxVal[i][bit][0] = s[i]-1;
				sum[i][bit][0] = p[i];
			}
		}
	}
	for(int bit = 0; bit < MAX_BIT; bit++){
		jump[n][bit][0] = n;
		maxVal[n][bit][0] = INF;
		sum[n][bit][0] = 0;
	}
	for(int l = 1; l < MAX_JUMP; l++){
		for(int i = 0; i <= n; i++){
			for(int bit = 0; bit < MAX_BIT; bit++){
				int a, b, c, d;
				a = jump[i][bit][l-1];
				b = jump[a][bit][l-1];
				c = jump[b][bit][l-1];
				d = jump[c][bit][l-1];
				jump[i][bit][l] = d;
				sum[i][bit][l] = sum[i][bit][l-1] + sum[a][bit][l-1] + sum[b][bit][l-1] + sum[c][bit][l-1];
				maxVal[i][bit][l] = min(min(maxVal[i][bit][l-1], maxVal[a][bit][l-1] - sum[i][bit][l-1]),min(maxVal[b][bit][l-1] - sum[a][bit][l-1]  - sum[i][bit][l-1], maxVal[c][bit][l-1] - sum[b][bit][l-1] - sum[a][bit][l-1] - sum[i][bit][l-1])); 
			}
		}
	}
}

long long simulate(int x, int z){
	long long val = z;
	int bit = 0;
	int xd = 1;
	while(bit < MAX_BIT-1 && 4 * xd <= val){
		bit++; xd *= 4;
	}
	while(x != N){
		for(int i = MAX_JUMP-1; i >= 0; i--){
			while(x != N && val <= maxVal[x][bit][i]){
				val += sum[x][bit][i];
				x = jump[x][bit][i];
			}
		}
		if(x != N){
			val += sum[x][MAX_BIT -1][0];
			x = jump[x][MAX_BIT-1][0];
		}
		while(bit < MAX_BIT-1 && 4 * xd <= val){
			bit++; xd *= 4;
		}
	}
	return val;
}

/*
int main(){
	int n, q; cin>>n>>q;
	vector<int> s(n), p(n), w(n), l(n);
	for(int i = 0; i < n; i++)cin>>s[i];
	for(int i = 0; i < n; i++)cin>>p[i];
	for(int i = 0; i < n; i++)cin>>w[i];
	for(int i = 0; i < n; i++)cin>>l[i];
	init(n, s, p, w, l);
	for(int j = 0; j < q; j++){
		int x, z; cin>>x>>z;
		cout<<simulate(x, z)<<"\n";
	}
}
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 11 ms 6480 KB Output is correct
4 Correct 436 ms 154552 KB Output is correct
5 Correct 8 ms 6484 KB Output is correct
6 Correct 405 ms 154468 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3412 KB Output is correct
2 Correct 3839 ms 1234808 KB Output is correct
3 Correct 4132 ms 1235052 KB Output is correct
4 Correct 3448 ms 1235048 KB Output is correct
5 Correct 2753 ms 1234928 KB Output is correct
6 Correct 3695 ms 1234892 KB Output is correct
7 Correct 3463 ms 1234948 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3412 KB Output is correct
2 Correct 442 ms 155436 KB Output is correct
3 Correct 338 ms 155512 KB Output is correct
4 Correct 334 ms 155436 KB Output is correct
5 Correct 330 ms 155216 KB Output is correct
6 Correct 419 ms 155380 KB Output is correct
7 Correct 384 ms 155384 KB Output is correct
8 Correct 334 ms 155412 KB Output is correct
9 Correct 332 ms 155340 KB Output is correct
10 Correct 318 ms 155420 KB Output is correct
11 Correct 541 ms 155260 KB Output is correct
12 Correct 796 ms 155240 KB Output is correct
13 Correct 471 ms 155340 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3412 KB Output is correct
2 Correct 442 ms 155436 KB Output is correct
3 Correct 338 ms 155512 KB Output is correct
4 Correct 334 ms 155436 KB Output is correct
5 Correct 330 ms 155216 KB Output is correct
6 Correct 419 ms 155380 KB Output is correct
7 Correct 384 ms 155384 KB Output is correct
8 Correct 334 ms 155412 KB Output is correct
9 Correct 332 ms 155340 KB Output is correct
10 Correct 318 ms 155420 KB Output is correct
11 Correct 541 ms 155260 KB Output is correct
12 Correct 796 ms 155240 KB Output is correct
13 Correct 471 ms 155340 KB Output is correct
14 Correct 5 ms 3412 KB Output is correct
15 Correct 360 ms 155212 KB Output is correct
16 Correct 469 ms 155380 KB Output is correct
17 Correct 385 ms 155212 KB Output is correct
18 Correct 398 ms 155300 KB Output is correct
19 Correct 441 ms 155208 KB Output is correct
20 Correct 434 ms 155328 KB Output is correct
21 Correct 417 ms 155340 KB Output is correct
22 Correct 341 ms 155192 KB Output is correct
23 Correct 567 ms 155436 KB Output is correct
24 Correct 798 ms 155372 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3412 KB Output is correct
2 Correct 442 ms 155436 KB Output is correct
3 Correct 338 ms 155512 KB Output is correct
4 Correct 334 ms 155436 KB Output is correct
5 Correct 330 ms 155216 KB Output is correct
6 Correct 419 ms 155380 KB Output is correct
7 Correct 384 ms 155384 KB Output is correct
8 Correct 334 ms 155412 KB Output is correct
9 Correct 332 ms 155340 KB Output is correct
10 Correct 318 ms 155420 KB Output is correct
11 Correct 541 ms 155260 KB Output is correct
12 Correct 796 ms 155240 KB Output is correct
13 Correct 471 ms 155340 KB Output is correct
14 Correct 5 ms 3412 KB Output is correct
15 Correct 360 ms 155212 KB Output is correct
16 Correct 469 ms 155380 KB Output is correct
17 Correct 385 ms 155212 KB Output is correct
18 Correct 398 ms 155300 KB Output is correct
19 Correct 441 ms 155208 KB Output is correct
20 Correct 434 ms 155328 KB Output is correct
21 Correct 417 ms 155340 KB Output is correct
22 Correct 341 ms 155192 KB Output is correct
23 Correct 567 ms 155436 KB Output is correct
24 Correct 798 ms 155372 KB Output is correct
25 Correct 506 ms 154528 KB Output is correct
26 Correct 492 ms 155304 KB Output is correct
27 Correct 414 ms 155340 KB Output is correct
28 Correct 372 ms 155244 KB Output is correct
29 Correct 511 ms 155288 KB Output is correct
30 Correct 599 ms 155348 KB Output is correct
31 Correct 579 ms 155252 KB Output is correct
32 Correct 877 ms 155324 KB Output is correct
33 Correct 1264 ms 155244 KB Output is correct
34 Correct 1448 ms 155156 KB Output is correct
35 Correct 857 ms 155292 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3412 KB Output is correct
2 Correct 3839 ms 1234808 KB Output is correct
3 Correct 4132 ms 1235052 KB Output is correct
4 Correct 3448 ms 1235048 KB Output is correct
5 Correct 2753 ms 1234928 KB Output is correct
6 Correct 3695 ms 1234892 KB Output is correct
7 Correct 3463 ms 1234948 KB Output is correct
8 Correct 4 ms 3412 KB Output is correct
9 Correct 442 ms 155436 KB Output is correct
10 Correct 338 ms 155512 KB Output is correct
11 Correct 334 ms 155436 KB Output is correct
12 Correct 330 ms 155216 KB Output is correct
13 Correct 419 ms 155380 KB Output is correct
14 Correct 384 ms 155384 KB Output is correct
15 Correct 334 ms 155412 KB Output is correct
16 Correct 332 ms 155340 KB Output is correct
17 Correct 318 ms 155420 KB Output is correct
18 Correct 541 ms 155260 KB Output is correct
19 Correct 796 ms 155240 KB Output is correct
20 Correct 471 ms 155340 KB Output is correct
21 Correct 5 ms 3412 KB Output is correct
22 Correct 360 ms 155212 KB Output is correct
23 Correct 469 ms 155380 KB Output is correct
24 Correct 385 ms 155212 KB Output is correct
25 Correct 398 ms 155300 KB Output is correct
26 Correct 441 ms 155208 KB Output is correct
27 Correct 434 ms 155328 KB Output is correct
28 Correct 417 ms 155340 KB Output is correct
29 Correct 341 ms 155192 KB Output is correct
30 Correct 567 ms 155436 KB Output is correct
31 Correct 798 ms 155372 KB Output is correct
32 Correct 506 ms 154528 KB Output is correct
33 Correct 492 ms 155304 KB Output is correct
34 Correct 414 ms 155340 KB Output is correct
35 Correct 372 ms 155244 KB Output is correct
36 Correct 511 ms 155288 KB Output is correct
37 Correct 599 ms 155348 KB Output is correct
38 Correct 579 ms 155252 KB Output is correct
39 Correct 877 ms 155324 KB Output is correct
40 Correct 1264 ms 155244 KB Output is correct
41 Correct 1448 ms 155156 KB Output is correct
42 Correct 857 ms 155292 KB Output is correct
43 Correct 0 ms 212 KB Output is correct
44 Correct 5 ms 3432 KB Output is correct
45 Correct 5661 ms 1235012 KB Output is correct
46 Correct 3862 ms 1234988 KB Output is correct
47 Correct 3907 ms 1234988 KB Output is correct
48 Correct 2655 ms 1234972 KB Output is correct
49 Correct 6507 ms 1235036 KB Output is correct
50 Correct 3692 ms 1234860 KB Output is correct
51 Correct 2526 ms 1234824 KB Output is correct
52 Correct 3805 ms 1235960 KB Output is correct
53 Execution timed out 7103 ms 1236048 KB Time limit exceeded
54 Halted 0 ms 0 KB -