oj.uz

Submission #817935

# Submission time Handle Problem Language Result Execution time Memory
817935 2023-08-09T20:50:25 Z Username4132 Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 159780 KB 
#include "dungeons.h"
#include<iostream>
#include <vector>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)

const int MAXN = 400010, LG = 21;
int s[MAXN], w[MAXN], l[MAXN], p[MAXN];
int n, up[LG][MAXN], mx[LG][MAXN];
ll cst[LG][MAXN];

void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
	n = _n;
	forn(i, n) s[i]=_s[i], p[i]=_p[i], w[i]=_w[i], l[i]=_l[i];
	w[n]=l[n]=n;
	s[n]=p[n]=0;
	forn(i, n+1){
		up[0][i]=w[i];
		cst[0][i]=s[i];
		mx[0][i]=s[i];
	}
	forn(i, LG-1) forn(j, n+1){
		up[i+1][j] = up[i][up[i][j]];
		mx[i+1][j] = max(mx[i][j], mx[i][up[i][j]]);
		cst[i+1][j] = cst[i][j] + cst[i][up[i][j]];
	}

	return;
}

long long simulate(int _x, int _z) {

	int x = _x;
	ll z = _z;
	while(x!=n){
		dforn(i, LG) if(mx[i][x] <= z){
			z += cst[i][x];
			x = up[i][x];
			// i = LG - 1;
		}
		if(s[x] <= z){
			z += s[x];
			x = w[x];
		}
		else{
			z += p[x];
			x = l[x];
		}
	}
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 0 ms 724 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 23 ms 19524 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 24 ms 19536 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1184 KB Output is correct
2 Correct 204 ms 151348 KB Output is correct
3 Correct 205 ms 158156 KB Output is correct
4 Correct 203 ms 159780 KB Output is correct
5 Correct 226 ms 159768 KB Output is correct
6 Correct 239 ms 158248 KB Output is correct
7 Correct 290 ms 156468 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 51 ms 20308 KB Output is correct
3 Correct 44 ms 20316 KB Output is correct
4 Correct 39 ms 20316 KB Output is correct
5 Correct 38 ms 20308 KB Output is correct
6 Execution timed out 7023 ms 20304 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 51 ms 20308 KB Output is correct
3 Correct 44 ms 20316 KB Output is correct
4 Correct 39 ms 20316 KB Output is correct
5 Correct 38 ms 20308 KB Output is correct
6 Execution timed out 7023 ms 20304 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 51 ms 20308 KB Output is correct
3 Correct 44 ms 20316 KB Output is correct
4 Correct 39 ms 20316 KB Output is correct
5 Correct 38 ms 20308 KB Output is correct
6 Execution timed out 7023 ms 20304 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1184 KB Output is correct
2 Correct 204 ms 151348 KB Output is correct
3 Correct 205 ms 158156 KB Output is correct
4 Correct 203 ms 159780 KB Output is correct
5 Correct 226 ms 159768 KB Output is correct
6 Correct 239 ms 158248 KB Output is correct
7 Correct 290 ms 156468 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 51 ms 20308 KB Output is correct
10 Correct 44 ms 20316 KB Output is correct
11 Correct 39 ms 20316 KB Output is correct
12 Correct 38 ms 20308 KB Output is correct
13 Execution timed out 7023 ms 20304 KB Time limit exceeded
14 Halted 0 ms 0 KB -