oj.uz

Submission #600376

# Submission time Handle Problem Language Result Execution time Memory
600376 2022-07-20T19:26:41 Z idiot123 Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1641984 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 3 to save memory
const int MAX_JUMP = 16;
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;
				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] = c;
				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]),maxVal[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 1 ms 300 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 13 ms 8532 KB Output is correct
4 Correct 500 ms 205544 KB Output is correct
5 Correct 11 ms 8532 KB Output is correct
6 Correct 488 ms 205520 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4460 KB Output is correct
2 Correct 4611 ms 1641984 KB Output is correct
3 Correct 4733 ms 1641932 KB Output is correct
4 Correct 4430 ms 1641848 KB Output is correct
5 Correct 3463 ms 1641880 KB Output is correct
6 Correct 4479 ms 1641848 KB Output is correct
7 Correct 4259 ms 1641848 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4436 KB Output is correct
2 Correct 525 ms 206208 KB Output is correct
3 Correct 447 ms 206224 KB Output is correct
4 Correct 450 ms 206128 KB Output is correct
5 Correct 429 ms 206240 KB Output is correct
6 Correct 494 ms 206300 KB Output is correct
7 Correct 485 ms 206188 KB Output is correct
8 Correct 443 ms 206296 KB Output is correct
9 Correct 436 ms 206156 KB Output is correct
10 Correct 422 ms 206300 KB Output is correct
11 Correct 677 ms 206180 KB Output is correct
12 Correct 858 ms 206260 KB Output is correct
13 Correct 605 ms 206076 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4436 KB Output is correct
2 Correct 525 ms 206208 KB Output is correct
3 Correct 447 ms 206224 KB Output is correct
4 Correct 450 ms 206128 KB Output is correct
5 Correct 429 ms 206240 KB Output is correct
6 Correct 494 ms 206300 KB Output is correct
7 Correct 485 ms 206188 KB Output is correct
8 Correct 443 ms 206296 KB Output is correct
9 Correct 436 ms 206156 KB Output is correct
10 Correct 422 ms 206300 KB Output is correct
11 Correct 677 ms 206180 KB Output is correct
12 Correct 858 ms 206260 KB Output is correct
13 Correct 605 ms 206076 KB Output is correct
14 Correct 6 ms 4436 KB Output is correct
15 Correct 458 ms 206160 KB Output is correct
16 Correct 548 ms 206192 KB Output is correct
17 Correct 497 ms 206296 KB Output is correct
18 Correct 488 ms 206188 KB Output is correct
19 Correct 526 ms 206176 KB Output is correct
20 Correct 560 ms 206184 KB Output is correct
21 Correct 552 ms 206180 KB Output is correct
22 Correct 448 ms 206156 KB Output is correct
23 Correct 645 ms 206180 KB Output is correct
24 Correct 906 ms 206184 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4436 KB Output is correct
2 Correct 525 ms 206208 KB Output is correct
3 Correct 447 ms 206224 KB Output is correct
4 Correct 450 ms 206128 KB Output is correct
5 Correct 429 ms 206240 KB Output is correct
6 Correct 494 ms 206300 KB Output is correct
7 Correct 485 ms 206188 KB Output is correct
8 Correct 443 ms 206296 KB Output is correct
9 Correct 436 ms 206156 KB Output is correct
10 Correct 422 ms 206300 KB Output is correct
11 Correct 677 ms 206180 KB Output is correct
12 Correct 858 ms 206260 KB Output is correct
13 Correct 605 ms 206076 KB Output is correct
14 Correct 6 ms 4436 KB Output is correct
15 Correct 458 ms 206160 KB Output is correct
16 Correct 548 ms 206192 KB Output is correct
17 Correct 497 ms 206296 KB Output is correct
18 Correct 488 ms 206188 KB Output is correct
19 Correct 526 ms 206176 KB Output is correct
20 Correct 560 ms 206184 KB Output is correct
21 Correct 552 ms 206180 KB Output is correct
22 Correct 448 ms 206156 KB Output is correct
23 Correct 645 ms 206180 KB Output is correct
24 Correct 906 ms 206184 KB Output is correct
25 Correct 607 ms 205384 KB Output is correct
26 Correct 541 ms 206184 KB Output is correct
27 Correct 516 ms 206188 KB Output is correct
28 Correct 483 ms 206292 KB Output is correct
29 Correct 560 ms 206184 KB Output is correct
30 Correct 683 ms 206176 KB Output is correct
31 Correct 691 ms 206112 KB Output is correct
32 Correct 929 ms 206280 KB Output is correct
33 Correct 1022 ms 206156 KB Output is correct
34 Correct 1380 ms 205992 KB Output is correct
35 Correct 882 ms 206156 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4460 KB Output is correct
2 Correct 4611 ms 1641984 KB Output is correct
3 Correct 4733 ms 1641932 KB Output is correct
4 Correct 4430 ms 1641848 KB Output is correct
5 Correct 3463 ms 1641880 KB Output is correct
6 Correct 4479 ms 1641848 KB Output is correct
7 Correct 4259 ms 1641848 KB Output is correct
8 Correct 4 ms 4436 KB Output is correct
9 Correct 525 ms 206208 KB Output is correct
10 Correct 447 ms 206224 KB Output is correct
11 Correct 450 ms 206128 KB Output is correct
12 Correct 429 ms 206240 KB Output is correct
13 Correct 494 ms 206300 KB Output is correct
14 Correct 485 ms 206188 KB Output is correct
15 Correct 443 ms 206296 KB Output is correct
16 Correct 436 ms 206156 KB Output is correct
17 Correct 422 ms 206300 KB Output is correct
18 Correct 677 ms 206180 KB Output is correct
19 Correct 858 ms 206260 KB Output is correct
20 Correct 605 ms 206076 KB Output is correct
21 Correct 6 ms 4436 KB Output is correct
22 Correct 458 ms 206160 KB Output is correct
23 Correct 548 ms 206192 KB Output is correct
24 Correct 497 ms 206296 KB Output is correct
25 Correct 488 ms 206188 KB Output is correct
26 Correct 526 ms 206176 KB Output is correct
27 Correct 560 ms 206184 KB Output is correct
28 Correct 552 ms 206180 KB Output is correct
29 Correct 448 ms 206156 KB Output is correct
30 Correct 645 ms 206180 KB Output is correct
31 Correct 906 ms 206184 KB Output is correct
32 Correct 607 ms 205384 KB Output is correct
33 Correct 541 ms 206184 KB Output is correct
34 Correct 516 ms 206188 KB Output is correct
35 Correct 483 ms 206292 KB Output is correct
36 Correct 560 ms 206184 KB Output is correct
37 Correct 683 ms 206176 KB Output is correct
38 Correct 691 ms 206112 KB Output is correct
39 Correct 929 ms 206280 KB Output is correct
40 Correct 1022 ms 206156 KB Output is correct
41 Correct 1380 ms 205992 KB Output is correct
42 Correct 882 ms 206156 KB Output is correct
43 Correct 0 ms 212 KB Output is correct
44 Correct 5 ms 4436 KB Output is correct
45 Correct 6177 ms 1641788 KB Output is correct
46 Correct 4501 ms 1641848 KB Output is correct
47 Correct 4565 ms 1641840 KB Output is correct
48 Correct 3331 ms 1641884 KB Output is correct
49 Correct 6810 ms 1641856 KB Output is correct
50 Correct 4335 ms 1641768 KB Output is correct
51 Correct 3088 ms 1641788 KB Output is correct
52 Correct 4316 ms 1641792 KB Output is correct
53 Execution timed out 7165 ms 1641856 KB Time limit exceeded
54 Halted 0 ms 0 KB -