oj.uz

Submission #1050825

# Submission time Handle Problem Language Result Execution time Memory
1050825 2024-08-09T14:56:01 Z Blagoj Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1651128 KB 
#include <bits/stdc++.h>
#include "dungeons.h"

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;

#define ll long long
#define inf 1e12

const int mxn = 4e5 + 10, LOG1 = 23, LOG2 = 9, BASE = 8;
//						  steps,     pwr
int n;
vector<int> s, p, w, l;
int go[mxn][LOG1][LOG2];
ll gain[mxn][LOG1][LOG2], lim[mxn][LOG1][LOG2];
ll F[LOG2];

void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
	F[0] = 1;
	for (int i = 1; i < LOG2; i++) F[i] = F[i - 1] * BASE;
	n = _n, s = _s, p = _p, w = _w, l = _l;
	for (int pwr = 0; pwr < LOG2; pwr++) {
		for (int i = 0; i < n; i++) {
			if (F[pwr] >= s[i]) {
				if (w[i] == n) go[i][0][pwr] = -1;
				else {
					go[i][0][pwr] = w[i];
					gain[i][0][pwr] = s[i];
					lim[i][0][pwr] = inf;
				}
			}
			else {
				if (l[i] == n) go[i][0][pwr] = -1;
				else {
					go[i][0][pwr] = l[i];
					gain[i][0][pwr] = p[i];
					lim[i][0][pwr] = s[i];
				}
			}
		}
	}	
	for (int steps = 1; steps < LOG1; steps++) {
		for (int pwr = 0; pwr < LOG2; pwr++) {
			for (int i = 0; i < n; i++) {
				int nxt = go[i][steps - 1][pwr];
				if (go[i][steps - 1][pwr] == -1 || go[nxt][steps - 1][pwr] == -1) go[i][steps][pwr] = -1;
				else {
					go[i][steps][pwr] = go[nxt][steps - 1][pwr];
					gain[i][steps][pwr] = gain[i][steps - 1][pwr] + gain[nxt][steps - 1][pwr];
					lim[i][steps][pwr] = min(lim[i][steps - 1][pwr], lim[nxt][steps - 1][pwr] - gain[i][steps - 1][pwr]);
				}
			}
		}
	}
}

ll simulate(int x, int z) {
	ll ans = z;
	int pwr = 0;
	while (x != n) { 
		while (pwr + 1 < LOG2 && F[pwr + 1] <= ans) pwr++;
		for (int i = LOG1 - 1; i >= 0; i--) {
			if (go[x][i][pwr] == -1) continue;
			if (ans >= lim[x][i][pwr]) continue;
			ans += gain[x][i][pwr];
			x = go[x][i][pwr];
		}
		if (ans >= s[x]) {
			ans += s[x];
			x = w[x];
		}
		else {
			ans += p[x];
			x = l[x];
		}
	}
	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4544 KB Output is correct
3 Correct 3 ms 15100 KB Output is correct
4 Correct 132 ms 209276 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 131 ms 209388 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 2571 ms 1647300 KB Output is correct
3 Correct 2700 ms 1647052 KB Output is correct
4 Correct 2565 ms 1648260 KB Output is correct
5 Correct 2215 ms 1648556 KB Output is correct
6 Correct 2628 ms 1647040 KB Output is correct
7 Correct 2644 ms 1645500 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 216 ms 210512 KB Output is correct
3 Correct 196 ms 210760 KB Output is correct
4 Correct 153 ms 210000 KB Output is correct
5 Correct 168 ms 210000 KB Output is correct
6 Correct 177 ms 210316 KB Output is correct
7 Correct 172 ms 210260 KB Output is correct
8 Correct 155 ms 210096 KB Output is correct
9 Correct 123 ms 210004 KB Output is correct
10 Correct 148 ms 209748 KB Output is correct
11 Correct 166 ms 210308 KB Output is correct
12 Correct 378 ms 210252 KB Output is correct
13 Correct 331 ms 210256 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 216 ms 210512 KB Output is correct
3 Correct 196 ms 210760 KB Output is correct
4 Correct 153 ms 210000 KB Output is correct
5 Correct 168 ms 210000 KB Output is correct
6 Correct 177 ms 210316 KB Output is correct
7 Correct 172 ms 210260 KB Output is correct
8 Correct 155 ms 210096 KB Output is correct
9 Correct 123 ms 210004 KB Output is correct
10 Correct 148 ms 209748 KB Output is correct
11 Correct 166 ms 210308 KB Output is correct
12 Correct 378 ms 210252 KB Output is correct
13 Correct 331 ms 210256 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 197 ms 210440 KB Output is correct
16 Correct 186 ms 210560 KB Output is correct
17 Correct 165 ms 210004 KB Output is correct
18 Correct 166 ms 210244 KB Output is correct
19 Correct 192 ms 210260 KB Output is correct
20 Correct 190 ms 210000 KB Output is correct
21 Correct 181 ms 210004 KB Output is correct
22 Correct 163 ms 210004 KB Output is correct
23 Correct 173 ms 210256 KB Output is correct
24 Correct 268 ms 210304 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 216 ms 210512 KB Output is correct
3 Correct 196 ms 210760 KB Output is correct
4 Correct 153 ms 210000 KB Output is correct
5 Correct 168 ms 210000 KB Output is correct
6 Correct 177 ms 210316 KB Output is correct
7 Correct 172 ms 210260 KB Output is correct
8 Correct 155 ms 210096 KB Output is correct
9 Correct 123 ms 210004 KB Output is correct
10 Correct 148 ms 209748 KB Output is correct
11 Correct 166 ms 210308 KB Output is correct
12 Correct 378 ms 210252 KB Output is correct
13 Correct 331 ms 210256 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 197 ms 210440 KB Output is correct
16 Correct 186 ms 210560 KB Output is correct
17 Correct 165 ms 210004 KB Output is correct
18 Correct 166 ms 210244 KB Output is correct
19 Correct 192 ms 210260 KB Output is correct
20 Correct 190 ms 210000 KB Output is correct
21 Correct 181 ms 210004 KB Output is correct
22 Correct 163 ms 210004 KB Output is correct
23 Correct 173 ms 210256 KB Output is correct
24 Correct 268 ms 210304 KB Output is correct
25 Correct 159 ms 209492 KB Output is correct
26 Correct 181 ms 210564 KB Output is correct
27 Correct 161 ms 210000 KB Output is correct
28 Correct 166 ms 210008 KB Output is correct
29 Correct 230 ms 210512 KB Output is correct
30 Correct 207 ms 210236 KB Output is correct
31 Correct 212 ms 210000 KB Output is correct
32 Correct 236 ms 210180 KB Output is correct
33 Correct 354 ms 210004 KB Output is correct
34 Correct 851 ms 210100 KB Output is correct
35 Correct 276 ms 210000 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 2571 ms 1647300 KB Output is correct
3 Correct 2700 ms 1647052 KB Output is correct
4 Correct 2565 ms 1648260 KB Output is correct
5 Correct 2215 ms 1648556 KB Output is correct
6 Correct 2628 ms 1647040 KB Output is correct
7 Correct 2644 ms 1645500 KB Output is correct
8 Correct 2 ms 10840 KB Output is correct
9 Correct 216 ms 210512 KB Output is correct
10 Correct 196 ms 210760 KB Output is correct
11 Correct 153 ms 210000 KB Output is correct
12 Correct 168 ms 210000 KB Output is correct
13 Correct 177 ms 210316 KB Output is correct
14 Correct 172 ms 210260 KB Output is correct
15 Correct 155 ms 210096 KB Output is correct
16 Correct 123 ms 210004 KB Output is correct
17 Correct 148 ms 209748 KB Output is correct
18 Correct 166 ms 210308 KB Output is correct
19 Correct 378 ms 210252 KB Output is correct
20 Correct 331 ms 210256 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 197 ms 210440 KB Output is correct
23 Correct 186 ms 210560 KB Output is correct
24 Correct 165 ms 210004 KB Output is correct
25 Correct 166 ms 210244 KB Output is correct
26 Correct 192 ms 210260 KB Output is correct
27 Correct 190 ms 210000 KB Output is correct
28 Correct 181 ms 210004 KB Output is correct
29 Correct 163 ms 210004 KB Output is correct
30 Correct 173 ms 210256 KB Output is correct
31 Correct 268 ms 210304 KB Output is correct
32 Correct 159 ms 209492 KB Output is correct
33 Correct 181 ms 210564 KB Output is correct
34 Correct 161 ms 210000 KB Output is correct
35 Correct 166 ms 210008 KB Output is correct
36 Correct 230 ms 210512 KB Output is correct
37 Correct 207 ms 210236 KB Output is correct
38 Correct 212 ms 210000 KB Output is correct
39 Correct 236 ms 210180 KB Output is correct
40 Correct 354 ms 210004 KB Output is correct
41 Correct 851 ms 210100 KB Output is correct
42 Correct 276 ms 210000 KB Output is correct
43 Correct 2 ms 4444 KB Output is correct
44 Correct 2 ms 10844 KB Output is correct
45 Correct 2486 ms 1651128 KB Output is correct
46 Correct 2335 ms 1647232 KB Output is correct
47 Correct 2364 ms 1647448 KB Output is correct
48 Execution timed out 7179 ms 1644164 KB Time limit exceeded
49 Halted 0 ms 0 KB -