oj.uz

Submission #1048907

# Submission time Handle Problem Language Result Execution time Memory
1048907 2024-08-08T10:50:09 Z AmirAli_H1 Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 244044 KB 
// In the name of Allah

#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;

typedef		long long				ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;

#define		endl					'\n'
#define		sep						' '
#define		F						first
#define		S						second
#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		pb						push_back
#define		Mp						make_pair

int n, q; bool ok = 1;
const int maxn = 4e5 + 7;
const int maxlg = 20, maxlgx = 25;
const ll oo = 1e18 + 4;
ll val1[maxn], val2[maxn], A1[maxn], A2[maxn];
ll sm[maxn], valx[maxn];
ll mx[maxn][maxlg]; int up[maxn][maxlg];
ll Ax[maxn][maxlgx]; int upx[maxn][maxlgx];

void init(int Nx, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
	n = Nx;
	for (int i = 0; i < n; i++) {
		A1[i] = w[i]; A2[i] = l[i];
		val1[i] = s[i]; val2[i] = p[i];
		if (val1[i] != val1[0]) ok = 0;
	}
	A1[n] = n; val1[n] = 0;
	A2[n] = n; val2[n] = 0;
	
	sm[n] = 0; valx[n] = 0;
	for (int i = n - 1; i >= 0; i--) {
		int j = A1[i];
		sm[i] = sm[j] + val1[i];
		valx[i] = val1[i] + sm[i];
	}
	
	for (int i = n; i >= 0; i--) {
		up[i][0] = A1[i]; mx[i][0] = valx[i];
		for (int j = 1; j < maxlg; j++) {
			int r = up[i][j - 1];
			up[i][j] = up[r][j - 1]; mx[i][j] = max(mx[i][j - 1], mx[r][j - 1]);
		}
	}
	
	for (int j = 0; j < maxlgx; j++) {
		for (int i = 0; i <= n; i++) {
			if (j == 0) {
				upx[i][j] = A2[i]; Ax[i][j] = val2[i];
			}
			else {
				int r = upx[i][j - 1];
				upx[i][j] = upx[r][j - 1];
				Ax[i][j] = min(oo, Ax[i][j - 1] + Ax[r][j - 1]);
			}
		}
	}
}

ll cal(int i, ll x) {
	if (i == n) return x;
	if (x < val1[i]) return cal(A2[i], x + val2[i]);
	
	ll R = x + sm[i];
	for (int j = maxlg - 1; j >= 0; j--) {
		if (mx[i][j] <= R) {
			x += sm[i]; x -= sm[up[i][j]];
			i = up[i][j];
		}
	}
	return cal(i, x);
}

ll calx(int i, ll x) {
	if (i == n) return x;
	if (x >= val1[i]) return x + sm[i];
	
	for (int j = maxlgx - 1; j >= 0; j--) {
		if (x + Ax[i][j] < val1[i]) {
			x += Ax[i][j]; i = upx[i][j];
		}
	}
	x += Ax[i][0]; i = upx[i][0];
	return x + sm[i];
}

ll simulate(int x, int z) {
	if (!ok) return cal(x, z);
	else return calx(x, z);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18884 KB Output is correct
3 Correct 3 ms 23132 KB Output is correct
4 Correct 25 ms 53276 KB Output is correct
5 Correct 4 ms 23132 KB Output is correct
6 Correct 25 ms 53452 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 21084 KB Output is correct
2 Correct 264 ms 244044 KB Output is correct
3 Correct 257 ms 243796 KB Output is correct
4 Correct 246 ms 243768 KB Output is correct
5 Correct 277 ms 243884 KB Output is correct
6 Correct 270 ms 243772 KB Output is correct
7 Correct 254 ms 243796 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21080 KB Output is correct
2 Correct 34 ms 54052 KB Output is correct
3 Correct 33 ms 54248 KB Output is correct
4 Correct 30 ms 54104 KB Output is correct
5 Correct 28 ms 54108 KB Output is correct
6 Correct 36 ms 54256 KB Output is correct
7 Correct 42 ms 54252 KB Output is correct
8 Correct 34 ms 54108 KB Output is correct
9 Correct 31 ms 54076 KB Output is correct
10 Correct 29 ms 54104 KB Output is correct
11 Correct 32 ms 54104 KB Output is correct
12 Correct 47 ms 54076 KB Output is correct
13 Correct 45 ms 54284 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21080 KB Output is correct
2 Correct 34 ms 54052 KB Output is correct
3 Correct 33 ms 54248 KB Output is correct
4 Correct 30 ms 54104 KB Output is correct
5 Correct 28 ms 54108 KB Output is correct
6 Correct 36 ms 54256 KB Output is correct
7 Correct 42 ms 54252 KB Output is correct
8 Correct 34 ms 54108 KB Output is correct
9 Correct 31 ms 54076 KB Output is correct
10 Correct 29 ms 54104 KB Output is correct
11 Correct 32 ms 54104 KB Output is correct
12 Correct 47 ms 54076 KB Output is correct
13 Correct 45 ms 54284 KB Output is correct
14 Correct 2 ms 21084 KB Output is correct
15 Correct 70 ms 54244 KB Output is correct
16 Correct 45 ms 54196 KB Output is correct
17 Correct 33 ms 54104 KB Output is correct
18 Correct 38 ms 54104 KB Output is correct
19 Correct 3291 ms 54128 KB Output is correct
20 Correct 75 ms 54104 KB Output is correct
21 Correct 39 ms 54104 KB Output is correct
22 Correct 5328 ms 54108 KB Output is correct
23 Execution timed out 7070 ms 54108 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21080 KB Output is correct
2 Correct 34 ms 54052 KB Output is correct
3 Correct 33 ms 54248 KB Output is correct
4 Correct 30 ms 54104 KB Output is correct
5 Correct 28 ms 54108 KB Output is correct
6 Correct 36 ms 54256 KB Output is correct
7 Correct 42 ms 54252 KB Output is correct
8 Correct 34 ms 54108 KB Output is correct
9 Correct 31 ms 54076 KB Output is correct
10 Correct 29 ms 54104 KB Output is correct
11 Correct 32 ms 54104 KB Output is correct
12 Correct 47 ms 54076 KB Output is correct
13 Correct 45 ms 54284 KB Output is correct
14 Correct 2 ms 21084 KB Output is correct
15 Correct 70 ms 54244 KB Output is correct
16 Correct 45 ms 54196 KB Output is correct
17 Correct 33 ms 54104 KB Output is correct
18 Correct 38 ms 54104 KB Output is correct
19 Correct 3291 ms 54128 KB Output is correct
20 Correct 75 ms 54104 KB Output is correct
21 Correct 39 ms 54104 KB Output is correct
22 Correct 5328 ms 54108 KB Output is correct
23 Execution timed out 7070 ms 54108 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 21084 KB Output is correct
2 Correct 264 ms 244044 KB Output is correct
3 Correct 257 ms 243796 KB Output is correct
4 Correct 246 ms 243768 KB Output is correct
5 Correct 277 ms 243884 KB Output is correct
6 Correct 270 ms 243772 KB Output is correct
7 Correct 254 ms 243796 KB Output is correct
8 Correct 3 ms 21080 KB Output is correct
9 Correct 34 ms 54052 KB Output is correct
10 Correct 33 ms 54248 KB Output is correct
11 Correct 30 ms 54104 KB Output is correct
12 Correct 28 ms 54108 KB Output is correct
13 Correct 36 ms 54256 KB Output is correct
14 Correct 42 ms 54252 KB Output is correct
15 Correct 34 ms 54108 KB Output is correct
16 Correct 31 ms 54076 KB Output is correct
17 Correct 29 ms 54104 KB Output is correct
18 Correct 32 ms 54104 KB Output is correct
19 Correct 47 ms 54076 KB Output is correct
20 Correct 45 ms 54284 KB Output is correct
21 Correct 2 ms 21084 KB Output is correct
22 Correct 70 ms 54244 KB Output is correct
23 Correct 45 ms 54196 KB Output is correct
24 Correct 33 ms 54104 KB Output is correct
25 Correct 38 ms 54104 KB Output is correct
26 Correct 3291 ms 54128 KB Output is correct
27 Correct 75 ms 54104 KB Output is correct
28 Correct 39 ms 54104 KB Output is correct
29 Correct 5328 ms 54108 KB Output is correct
30 Execution timed out 7070 ms 54108 KB Time limit exceeded
31 Halted 0 ms 0 KB -