oj.uz

Submission #852279

# Submission time Handle Problem Language Result Execution time Memory
852279 2023-09-21T14:14:40 Z alex_2008 Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3339 ms 1427824 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
#define mindiff first
#define pos second.first
#define strength second.second
using namespace std;
const long long N = 4e5 + 10;
const long long M = 10000001;
const int INF = 1e7;
pair<int, pair<int, int>> dp[N][12][24];
long long NN;
vector <long long> ss, pp, ww, ll;
long long nxt[N];
int lg4[M];
bool ch = true;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
  	for (int i = 1; i < 4; i++) {
  		lg4[i] = 0;
  	}
  	for (int i = 4; i < M; i++) {
		lg4[i] = lg4[i / 4] + 1;
    } 
  	NN = n;
	s.push_back(0);
	p.push_back(0);
	w.push_back(n);
	l.push_back(n);
	for (int i = 0; i <= n; i++) {
		ss.push_back(s[i]);
		if (w[i] != l[i]) ch = false;
    }
	nxt[n] = 0;
	for (int i = n - 1; i >= 0; i--) {
		nxt[i] = s[i] + nxt[w[i]];
	}
	for (int i = 0; i <= n; i++) {
		pp.push_back(p[i]);
	}
	for (int i = 0; i <= n; i++) {
		ww.push_back(w[i]);
	}
	for (int i = 0; i <= n; i++) {
		ll.push_back(l[i]);
	}
	for (int k = 0; k < 24; k++) {
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j < 12; j++) {
				if (k == 0) {
					dp[i][j][k].pos = ((1 << (2 * j)) >= s[i]) ? w[i] : l[i];
					dp[i][j][k].strength = ((1 << (2 * j)) >= s[i]) ? s[i] : p[i];
					dp[i][j][k].mindiff = ((1 << (2 * j)) < s[i]) ? s[i] : INF;
				}
				else {
					int p = dp[i][j][k - 1].pos;
					dp[i][j][k].pos = dp[p][j][k - 1].pos;
					dp[i][j][k].strength = min(INF, dp[i][j][k - 1].strength + dp[p][j][k - 1].strength);
					dp[i][j][k].mindiff = max(0, min(dp[i][j][k - 1].mindiff, dp[p][j][k - 1].mindiff - dp[i][j][k - 1].strength));
				}
			}
		}
	}
}
long long simulate(int xx, int zz) {
	long long x = xx, z = zz;
	while (1) {
		if (z >= 10000000) {
			z += nxt[x];
			return z;
		}
		int v = lg4[z];
		for (int k = 23; k >= 0; k--) {
			if (dp[x][v][k].pos == N || dp[x][v][k].mindiff <= z || (dp[x][v][k].strength + z >= 10000000) || lg4[dp[x][v][k].strength + z] > v) continue;
			z += dp[x][v][k].strength;
			x = dp[x][v][k].pos;
		}
		if (z >= ss[x]) {
			z += ss[x];
			x = ww[x];
		}
		else {
			z += pp[x];
			x = ll[x];
		}
		if (x == NN) return z;
	}
	return 0;
}
//int main() {
//	init(3, { 2, 6, 9 }, { 3, 1, 2 }, { 2, 2, 3 }, { 1, 0, 1 });
//	cout << simulate(0, 1) << "\n";
//	cout << simulate(2, 3) << "\n";
//}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 41560 KB Output is correct
2 Correct 11 ms 41560 KB Output is correct
3 Correct 14 ms 47960 KB Output is correct
4 Correct 185 ms 215240 KB Output is correct
5 Correct 14 ms 47960 KB Output is correct
6 Correct 197 ms 215240 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45656 KB Output is correct
2 Correct 2347 ms 1427824 KB Output is correct
3 Correct 2456 ms 1427028 KB Output is correct
4 Correct 2300 ms 1423560 KB Output is correct
5 Correct 1524 ms 1424448 KB Output is correct
6 Correct 2622 ms 1424512 KB Output is correct
7 Correct 2629 ms 1426716 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45656 KB Output is correct
2 Correct 213 ms 216264 KB Output is correct
3 Correct 201 ms 216008 KB Output is correct
4 Correct 277 ms 216268 KB Output is correct
5 Correct 269 ms 216008 KB Output is correct
6 Correct 252 ms 216024 KB Output is correct
7 Correct 256 ms 216008 KB Output is correct
8 Correct 421 ms 216028 KB Output is correct
9 Correct 209 ms 216008 KB Output is correct
10 Correct 392 ms 216024 KB Output is correct
11 Correct 376 ms 216264 KB Output is correct
12 Correct 1043 ms 216008 KB Output is correct
13 Correct 1014 ms 216024 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45656 KB Output is correct
2 Correct 213 ms 216264 KB Output is correct
3 Correct 201 ms 216008 KB Output is correct
4 Correct 277 ms 216268 KB Output is correct
5 Correct 269 ms 216008 KB Output is correct
6 Correct 252 ms 216024 KB Output is correct
7 Correct 256 ms 216008 KB Output is correct
8 Correct 421 ms 216028 KB Output is correct
9 Correct 209 ms 216008 KB Output is correct
10 Correct 392 ms 216024 KB Output is correct
11 Correct 376 ms 216264 KB Output is correct
12 Correct 1043 ms 216008 KB Output is correct
13 Correct 1014 ms 216024 KB Output is correct
14 Correct 20 ms 45656 KB Output is correct
15 Correct 235 ms 216008 KB Output is correct
16 Correct 227 ms 216008 KB Output is correct
17 Correct 280 ms 216024 KB Output is correct
18 Correct 311 ms 216008 KB Output is correct
19 Correct 352 ms 216008 KB Output is correct
20 Correct 392 ms 216024 KB Output is correct
21 Correct 419 ms 216008 KB Output is correct
22 Correct 386 ms 216024 KB Output is correct
23 Correct 622 ms 215888 KB Output is correct
24 Correct 669 ms 216012 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45656 KB Output is correct
2 Correct 213 ms 216264 KB Output is correct
3 Correct 201 ms 216008 KB Output is correct
4 Correct 277 ms 216268 KB Output is correct
5 Correct 269 ms 216008 KB Output is correct
6 Correct 252 ms 216024 KB Output is correct
7 Correct 256 ms 216008 KB Output is correct
8 Correct 421 ms 216028 KB Output is correct
9 Correct 209 ms 216008 KB Output is correct
10 Correct 392 ms 216024 KB Output is correct
11 Correct 376 ms 216264 KB Output is correct
12 Correct 1043 ms 216008 KB Output is correct
13 Correct 1014 ms 216024 KB Output is correct
14 Correct 20 ms 45656 KB Output is correct
15 Correct 235 ms 216008 KB Output is correct
16 Correct 227 ms 216008 KB Output is correct
17 Correct 280 ms 216024 KB Output is correct
18 Correct 311 ms 216008 KB Output is correct
19 Correct 352 ms 216008 KB Output is correct
20 Correct 392 ms 216024 KB Output is correct
21 Correct 419 ms 216008 KB Output is correct
22 Correct 386 ms 216024 KB Output is correct
23 Correct 622 ms 215888 KB Output is correct
24 Correct 669 ms 216012 KB Output is correct
25 Correct 180 ms 215248 KB Output is correct
26 Correct 213 ms 216012 KB Output is correct
27 Correct 236 ms 216036 KB Output is correct
28 Correct 252 ms 215936 KB Output is correct
29 Correct 221 ms 216024 KB Output is correct
30 Correct 505 ms 216028 KB Output is correct
31 Correct 518 ms 216028 KB Output is correct
32 Correct 588 ms 216028 KB Output is correct
33 Correct 547 ms 215800 KB Output is correct
34 Correct 743 ms 216032 KB Output is correct
35 Correct 407 ms 216024 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45656 KB Output is correct
2 Correct 2347 ms 1427824 KB Output is correct
3 Correct 2456 ms 1427028 KB Output is correct
4 Correct 2300 ms 1423560 KB Output is correct
5 Correct 1524 ms 1424448 KB Output is correct
6 Correct 2622 ms 1424512 KB Output is correct
7 Correct 2629 ms 1426716 KB Output is correct
8 Correct 13 ms 45656 KB Output is correct
9 Correct 213 ms 216264 KB Output is correct
10 Correct 201 ms 216008 KB Output is correct
11 Correct 277 ms 216268 KB Output is correct
12 Correct 269 ms 216008 KB Output is correct
13 Correct 252 ms 216024 KB Output is correct
14 Correct 256 ms 216008 KB Output is correct
15 Correct 421 ms 216028 KB Output is correct
16 Correct 209 ms 216008 KB Output is correct
17 Correct 392 ms 216024 KB Output is correct
18 Correct 376 ms 216264 KB Output is correct
19 Correct 1043 ms 216008 KB Output is correct
20 Correct 1014 ms 216024 KB Output is correct
21 Correct 20 ms 45656 KB Output is correct
22 Correct 235 ms 216008 KB Output is correct
23 Correct 227 ms 216008 KB Output is correct
24 Correct 280 ms 216024 KB Output is correct
25 Correct 311 ms 216008 KB Output is correct
26 Correct 352 ms 216008 KB Output is correct
27 Correct 392 ms 216024 KB Output is correct
28 Correct 419 ms 216008 KB Output is correct
29 Correct 386 ms 216024 KB Output is correct
30 Correct 622 ms 215888 KB Output is correct
31 Correct 669 ms 216012 KB Output is correct
32 Correct 180 ms 215248 KB Output is correct
33 Correct 213 ms 216012 KB Output is correct
34 Correct 236 ms 216036 KB Output is correct
35 Correct 252 ms 215936 KB Output is correct
36 Correct 221 ms 216024 KB Output is correct
37 Correct 505 ms 216028 KB Output is correct
38 Correct 518 ms 216028 KB Output is correct
39 Correct 588 ms 216028 KB Output is correct
40 Correct 547 ms 215800 KB Output is correct
41 Correct 743 ms 216032 KB Output is correct
42 Correct 407 ms 216024 KB Output is correct
43 Correct 11 ms 41560 KB Output is correct
44 Correct 14 ms 45656 KB Output is correct
45 Correct 1811 ms 1424952 KB Output is correct
46 Correct 1729 ms 1423144 KB Output is correct
47 Correct 1714 ms 1423652 KB Output is correct
48 Correct 1559 ms 1423576 KB Output is correct
49 Correct 1671 ms 1422920 KB Output is correct
50 Correct 2416 ms 1426492 KB Output is correct
51 Correct 1393 ms 1423684 KB Output is correct
52 Correct 2387 ms 1424192 KB Output is correct
53 Correct 3339 ms 1423356 KB Output is correct
54 Correct 2699 ms 1423944 KB Output is correct
55 Correct 3173 ms 1423424 KB Output is correct
56 Correct 2711 ms 1423932 KB Output is correct
57 Correct 2892 ms 1423608 KB Output is correct
58 Correct 3050 ms 1424868 KB Output is correct
59 Correct 2854 ms 1423596 KB Output is correct
60 Correct 2938 ms 1423152 KB Output is correct
61 Correct 2644 ms 1424760 KB Output is correct