oj.uz

Submission #898950

# Submission time Handle Problem Language Result Execution time Memory
898950 2024-01-05T09:49:22 Z Trisanu_Das Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 265084 KB 
#include "dungeons.h"
 
#include <bits/stdc++.h>
using namespace std; 
 
typedef long long ll;
 
//------------------------------------------------ 

 
int N; 
vector<int> s, p, w, l; 
ll jump[400005][25], jumpSum[400005][25], jumpMX[400005][25];

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
	N=n; 
	::s=s; ::p=p; ::w=w; ::l=l; 
 
	::s.push_back(0); ::p.push_back(0); ::w.push_back(N); ::l.push_back(N); 
 
	for(int i = N; i >= 0; i--){
		if(i == N){
			for(int j = 0; j < 25; j++) jump[i][j] = i, jumpSum[i][j] = 0, jumpMX[i][j] = 0; 
		}
		else{
			jump[i][0] = w[i]; jumpSum[i][0] = s[i]; jumpMX[i][0] = max(s[i], s[w[i]]); 
			for(int j = 1; j < 25; j++){
				jump[i][j] = jump[jump[i][j - 1]][j - 1];
				jumpSum[i][j] = jumpSum[i][j - 1] + jumpSum[jump[i][j - 1]][j - 1];  
				jumpMX[i][j] = max(jumpMX[i][j - 1], jumpMX[jump[i][j - 1]][j - 1]); 
			}
		}
	}
 
}
 
ll simulate(int st, int x){
	int u = st; 
	ll X = x; 
	while(1){
		if(u == N) break;
		if(X >= s[u]){
			for(int i = 24; i >= 0; i--) if(jumpMX[u][i]<=X){
				X += jumpSum[u][i]; 
				u = jump[u][i]; 
			}
			X += jumpSum[u][0]; 
			u = jump[u][0]; 
		}
		else{
			X += p[u]; 
			u = l[u]; 
		}
		
	}
	return X; 
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 30 ms 33580 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 31 ms 33612 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 431 ms 256232 KB Output is correct
3 Correct 512 ms 264380 KB Output is correct
4 Correct 509 ms 264668 KB Output is correct
5 Correct 385 ms 264416 KB Output is correct
6 Correct 462 ms 265084 KB Output is correct
7 Correct 553 ms 260536 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 54 ms 35652 KB Output is correct
3 Correct 52 ms 35868 KB Output is correct
4 Correct 52 ms 35520 KB Output is correct
5 Correct 50 ms 35400 KB Output is correct
6 Execution timed out 7066 ms 35592 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 54 ms 35652 KB Output is correct
3 Correct 52 ms 35868 KB Output is correct
4 Correct 52 ms 35520 KB Output is correct
5 Correct 50 ms 35400 KB Output is correct
6 Execution timed out 7066 ms 35592 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 54 ms 35652 KB Output is correct
3 Correct 52 ms 35868 KB Output is correct
4 Correct 52 ms 35520 KB Output is correct
5 Correct 50 ms 35400 KB Output is correct
6 Execution timed out 7066 ms 35592 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 431 ms 256232 KB Output is correct
3 Correct 512 ms 264380 KB Output is correct
4 Correct 509 ms 264668 KB Output is correct
5 Correct 385 ms 264416 KB Output is correct
6 Correct 462 ms 265084 KB Output is correct
7 Correct 553 ms 260536 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 54 ms 35652 KB Output is correct
10 Correct 52 ms 35868 KB Output is correct
11 Correct 52 ms 35520 KB Output is correct
12 Correct 50 ms 35400 KB Output is correct
13 Execution timed out 7066 ms 35592 KB Time limit exceeded
14 Halted 0 ms 0 KB -