oj.uz

Submission #1050799

# Submission time Handle Problem Language Result Execution time Memory
1050799 2024-08-09T14:37:15 Z Blagoj Dungeons Game (IOI21_dungeons) C++17
63 / 100
 2202 ms 1728092 KB 
#include <bits/stdc++.h>
#include "dungeons.h"

using namespace std;

#define ll long long
#define inf 1e12

const int mxn = 1e5 + 100, LOG1 = 20, LOG2 = 28;
//						   steps,     pwr
int n;
vector<int> s, p, w, l;
ll go[mxn][LOG1][LOG2], gain[mxn][LOG1][LOG2], lim[mxn][LOG1][LOG2];

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;
	for (int pwr = 0; pwr < LOG2; pwr++) {
		for (int i = 0; i < n; i++) {
			if ((1LL << 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;
	while (x != n) {
		ll pwr = log2(ans);
		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 4444 KB Output is correct
3 Correct 6 ms 33372 KB Output is correct
4 Correct 551 ms 664108 KB Output is correct
5 Correct 9 ms 33372 KB Output is correct
6 Correct 542 ms 663984 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19036 KB Output is correct
2 Runtime error 837 ms 1728092 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19032 KB Output is correct
2 Correct 739 ms 665372 KB Output is correct
3 Correct 740 ms 665616 KB Output is correct
4 Correct 641 ms 664992 KB Output is correct
5 Correct 625 ms 664900 KB Output is correct
6 Correct 733 ms 665012 KB Output is correct
7 Correct 819 ms 665028 KB Output is correct
8 Correct 736 ms 664660 KB Output is correct
9 Correct 523 ms 664672 KB Output is correct
10 Correct 709 ms 664736 KB Output is correct
11 Correct 806 ms 665124 KB Output is correct
12 Correct 2202 ms 665172 KB Output is correct
13 Correct 1955 ms 664916 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19032 KB Output is correct
2 Correct 739 ms 665372 KB Output is correct
3 Correct 740 ms 665616 KB Output is correct
4 Correct 641 ms 664992 KB Output is correct
5 Correct 625 ms 664900 KB Output is correct
6 Correct 733 ms 665012 KB Output is correct
7 Correct 819 ms 665028 KB Output is correct
8 Correct 736 ms 664660 KB Output is correct
9 Correct 523 ms 664672 KB Output is correct
10 Correct 709 ms 664736 KB Output is correct
11 Correct 806 ms 665124 KB Output is correct
12 Correct 2202 ms 665172 KB Output is correct
13 Correct 1955 ms 664916 KB Output is correct
14 Correct 6 ms 19036 KB Output is correct
15 Correct 768 ms 665236 KB Output is correct
16 Correct 762 ms 665380 KB Output is correct
17 Correct 729 ms 664904 KB Output is correct
18 Correct 778 ms 664996 KB Output is correct
19 Correct 770 ms 665116 KB Output is correct
20 Correct 753 ms 664828 KB Output is correct
21 Correct 797 ms 664816 KB Output is correct
22 Correct 631 ms 664936 KB Output is correct
23 Correct 779 ms 665100 KB Output is correct
24 Correct 958 ms 665348 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19032 KB Output is correct
2 Correct 739 ms 665372 KB Output is correct
3 Correct 740 ms 665616 KB Output is correct
4 Correct 641 ms 664992 KB Output is correct
5 Correct 625 ms 664900 KB Output is correct
6 Correct 733 ms 665012 KB Output is correct
7 Correct 819 ms 665028 KB Output is correct
8 Correct 736 ms 664660 KB Output is correct
9 Correct 523 ms 664672 KB Output is correct
10 Correct 709 ms 664736 KB Output is correct
11 Correct 806 ms 665124 KB Output is correct
12 Correct 2202 ms 665172 KB Output is correct
13 Correct 1955 ms 664916 KB Output is correct
14 Correct 6 ms 19036 KB Output is correct
15 Correct 768 ms 665236 KB Output is correct
16 Correct 762 ms 665380 KB Output is correct
17 Correct 729 ms 664904 KB Output is correct
18 Correct 778 ms 664996 KB Output is correct
19 Correct 770 ms 665116 KB Output is correct
20 Correct 753 ms 664828 KB Output is correct
21 Correct 797 ms 664816 KB Output is correct
22 Correct 631 ms 664936 KB Output is correct
23 Correct 779 ms 665100 KB Output is correct
24 Correct 958 ms 665348 KB Output is correct
25 Correct 743 ms 664440 KB Output is correct
26 Correct 787 ms 665384 KB Output is correct
27 Correct 717 ms 664788 KB Output is correct
28 Correct 740 ms 664900 KB Output is correct
29 Correct 754 ms 665408 KB Output is correct
30 Correct 779 ms 664916 KB Output is correct
31 Correct 756 ms 664672 KB Output is correct
32 Correct 861 ms 664920 KB Output is correct
33 Correct 844 ms 664656 KB Output is correct
34 Correct 1594 ms 664720 KB Output is correct
35 Correct 985 ms 664808 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19036 KB Output is correct
2 Runtime error 837 ms 1728092 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -