oj.uz

Submission #488516

# Submission time Handle Problem Language Result Execution time Memory
488516 2021-11-19T12:28:55 Z 8e7 Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3958 ms 1157160 KB 
//Challenge: Accepted
#include "dungeons.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <assert.h>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 400005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int n;
vector<int> s, p, w, l, disp;
struct WIN{
	int anc[19][maxn];
	ll ma[19][maxn];
	ll sum[19][maxn];
	void build() {
		for (int i = 0;i < n;i++) {
			anc[0][i] = w[i];
			ma[0][i] = s[i];
			sum[0][i] = s[i];
		}
		anc[0][n] = n;
		for (int i = 1;i < 19;i++) {
			for (int j = 0;j <= n;j++) {
				anc[i][j] = anc[i-1][anc[i-1][j]];
				sum[i][j] = sum[i-1][j] + sum[i-1][anc[i-1][j]];
				ma[i][j] = max(ma[i-1][j], ma[i-1][anc[i-1][j]] - sum[i-1][j]);
			}
		}
	}
	void move(int &x, ll &val) { //brings it to the nearest loss
		for (int i = 18;i >= 0;i--) {
			if (val >= ma[i][x]) {
				val += sum[i][x];
				x = anc[i][x];
			}
		}
	}
} win;
const int inf = 1<<26;
struct LOSE{
	int anc[16][maxn];
	int mi[16][maxn];
	int sum[16][maxn];
	void build(int bit) {
		for (int i = 0;i < n;i++) {
			if (s[i] >= (1<<bit)) mi[0][i] = s[i];
			else mi[0][i] = 1<<(bit+2);
			if (s[i] < (1<<bit)) sum[0][i] = s[i], anc[0][i] = w[i];
			else sum[0][i] = p[i], anc[0][i] = l[i];
		}
		anc[0][n] = n;
		for (int i = 1;i < 16;i++) {
			for (int j = 0;j <= n;j++) {
				anc[i][j] = anc[i-1][anc[i-1][anc[i-1][j]]];
				sum[i][j] = min(inf, sum[i-1][j] + sum[i-1][anc[i-1][j]] + sum[i-1][anc[i-1][anc[i-1][j]]]);
				mi[i][j] = max(0, min(mi[i-1][j], min(mi[i-1][anc[i-1][j]] - sum[i-1][j], mi[i-1][anc[i-1][anc[i-1][j]]] - sum[i-1][j] - sum[i-1][anc[i-1][j]])));
			}
		}
	}
	void move(int &x, ll &val) { //brings it to the nearest win
		for (int i = 15;i >= 0;i--) {
			if (val < mi[i][x]) {
				val += sum[i][x];
				x = anc[i][x];
			}
			if (val < mi[i][x]) {
				val += sum[i][x];
				x = anc[i][x];
			}
		}
	}
} lose[13];
void init(int nv, vector<int> sv, vector<int> pv, vector<int> wv, vector<int> lv) {
	n = nv;
	s = sv, p = pv, w = wv, l = lv;	
	win.build();	
	for (int i = 0;i < 13;i++) lose[i].build(i*2);
	//lose.build();
}
 
 
long long simulate(int x, int z) {
	ll ans = z;
	for (int i = 0;i < 13 && x != n;i++) {
		for (int j = 0;j < 4;j++) {
			lose[i].move(x, ans);
			if (x != n && ans >= s[x]) {
				ans += s[x];
				x = w[x];
			}
		}
		win.move(x, ans);
	}
	return ans;
}
/*
3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3
 
3 3
14 14 14
2 1 1 
1 2 3
1 2 0
0 0
2 4
1 1
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5068 KB Output is correct
2 Correct 2 ms 5068 KB Output is correct
3 Correct 7 ms 10760 KB Output is correct
4 Correct 136 ms 147968 KB Output is correct
5 Correct 7 ms 10828 KB Output is correct
6 Correct 141 ms 147928 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 1028 ms 1145868 KB Output is correct
3 Correct 1057 ms 1146128 KB Output is correct
4 Correct 1037 ms 1145984 KB Output is correct
5 Correct 1145 ms 1146032 KB Output is correct
6 Correct 1039 ms 1146040 KB Output is correct
7 Correct 1033 ms 1146240 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 178 ms 148660 KB Output is correct
3 Correct 166 ms 148652 KB Output is correct
4 Correct 148 ms 148676 KB Output is correct
5 Correct 151 ms 148660 KB Output is correct
6 Correct 192 ms 148724 KB Output is correct
7 Correct 188 ms 148716 KB Output is correct
8 Correct 148 ms 148652 KB Output is correct
9 Correct 160 ms 148816 KB Output is correct
10 Correct 153 ms 148676 KB Output is correct
11 Correct 190 ms 149032 KB Output is correct
12 Correct 280 ms 149036 KB Output is correct
13 Correct 177 ms 149052 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 178 ms 148660 KB Output is correct
3 Correct 166 ms 148652 KB Output is correct
4 Correct 148 ms 148676 KB Output is correct
5 Correct 151 ms 148660 KB Output is correct
6 Correct 192 ms 148724 KB Output is correct
7 Correct 188 ms 148716 KB Output is correct
8 Correct 148 ms 148652 KB Output is correct
9 Correct 160 ms 148816 KB Output is correct
10 Correct 153 ms 148676 KB Output is correct
11 Correct 190 ms 149032 KB Output is correct
12 Correct 280 ms 149036 KB Output is correct
13 Correct 177 ms 149052 KB Output is correct
14 Correct 5 ms 8012 KB Output is correct
15 Correct 390 ms 149164 KB Output is correct
16 Correct 175 ms 149160 KB Output is correct
17 Correct 151 ms 149028 KB Output is correct
18 Correct 172 ms 149064 KB Output is correct
19 Correct 200 ms 149096 KB Output is correct
20 Correct 180 ms 149088 KB Output is correct
21 Correct 161 ms 149124 KB Output is correct
22 Correct 690 ms 149216 KB Output is correct
23 Correct 218 ms 149076 KB Output is correct
24 Correct 1953 ms 149048 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 178 ms 148660 KB Output is correct
3 Correct 166 ms 148652 KB Output is correct
4 Correct 148 ms 148676 KB Output is correct
5 Correct 151 ms 148660 KB Output is correct
6 Correct 192 ms 148724 KB Output is correct
7 Correct 188 ms 148716 KB Output is correct
8 Correct 148 ms 148652 KB Output is correct
9 Correct 160 ms 148816 KB Output is correct
10 Correct 153 ms 148676 KB Output is correct
11 Correct 190 ms 149032 KB Output is correct
12 Correct 280 ms 149036 KB Output is correct
13 Correct 177 ms 149052 KB Output is correct
14 Correct 5 ms 8012 KB Output is correct
15 Correct 390 ms 149164 KB Output is correct
16 Correct 175 ms 149160 KB Output is correct
17 Correct 151 ms 149028 KB Output is correct
18 Correct 172 ms 149064 KB Output is correct
19 Correct 200 ms 149096 KB Output is correct
20 Correct 180 ms 149088 KB Output is correct
21 Correct 161 ms 149124 KB Output is correct
22 Correct 690 ms 149216 KB Output is correct
23 Correct 218 ms 149076 KB Output is correct
24 Correct 1953 ms 149048 KB Output is correct
25 Correct 146 ms 148312 KB Output is correct
26 Correct 180 ms 148980 KB Output is correct
27 Correct 229 ms 148908 KB Output is correct
28 Correct 225 ms 148912 KB Output is correct
29 Correct 173 ms 148968 KB Output is correct
30 Correct 193 ms 148908 KB Output is correct
31 Correct 207 ms 148964 KB Output is correct
32 Correct 1382 ms 148904 KB Output is correct
33 Correct 538 ms 148880 KB Output is correct
34 Correct 795 ms 148908 KB Output is correct
35 Correct 1365 ms 148932 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 1028 ms 1145868 KB Output is correct
3 Correct 1057 ms 1146128 KB Output is correct
4 Correct 1037 ms 1145984 KB Output is correct
5 Correct 1145 ms 1146032 KB Output is correct
6 Correct 1039 ms 1146040 KB Output is correct
7 Correct 1033 ms 1146240 KB Output is correct
8 Correct 5 ms 8012 KB Output is correct
9 Correct 178 ms 148660 KB Output is correct
10 Correct 166 ms 148652 KB Output is correct
11 Correct 148 ms 148676 KB Output is correct
12 Correct 151 ms 148660 KB Output is correct
13 Correct 192 ms 148724 KB Output is correct
14 Correct 188 ms 148716 KB Output is correct
15 Correct 148 ms 148652 KB Output is correct
16 Correct 160 ms 148816 KB Output is correct
17 Correct 153 ms 148676 KB Output is correct
18 Correct 190 ms 149032 KB Output is correct
19 Correct 280 ms 149036 KB Output is correct
20 Correct 177 ms 149052 KB Output is correct
21 Correct 5 ms 8012 KB Output is correct
22 Correct 390 ms 149164 KB Output is correct
23 Correct 175 ms 149160 KB Output is correct
24 Correct 151 ms 149028 KB Output is correct
25 Correct 172 ms 149064 KB Output is correct
26 Correct 200 ms 149096 KB Output is correct
27 Correct 180 ms 149088 KB Output is correct
28 Correct 161 ms 149124 KB Output is correct
29 Correct 690 ms 149216 KB Output is correct
30 Correct 218 ms 149076 KB Output is correct
31 Correct 1953 ms 149048 KB Output is correct
32 Correct 146 ms 148312 KB Output is correct
33 Correct 180 ms 148980 KB Output is correct
34 Correct 229 ms 148908 KB Output is correct
35 Correct 225 ms 148912 KB Output is correct
36 Correct 173 ms 148968 KB Output is correct
37 Correct 193 ms 148908 KB Output is correct
38 Correct 207 ms 148964 KB Output is correct
39 Correct 1382 ms 148904 KB Output is correct
40 Correct 538 ms 148880 KB Output is correct
41 Correct 795 ms 148908 KB Output is correct
42 Correct 1365 ms 148932 KB Output is correct
43 Correct 3 ms 5072 KB Output is correct
44 Correct 6 ms 8004 KB Output is correct
45 Correct 1621 ms 1157144 KB Output is correct
46 Correct 1365 ms 1152568 KB Output is correct
47 Correct 1302 ms 1153080 KB Output is correct
48 Correct 1084 ms 1155132 KB Output is correct
49 Correct 1672 ms 1157160 KB Output is correct
50 Correct 1036 ms 1154728 KB Output is correct
51 Correct 1012 ms 1155124 KB Output is correct
52 Correct 1037 ms 1152828 KB Output is correct
53 Correct 3958 ms 1153588 KB Output is correct
54 Correct 1565 ms 1154860 KB Output is correct
55 Correct 1914 ms 1153692 KB Output is correct
56 Correct 3527 ms 1154376 KB Output is correct
57 Correct 3572 ms 1154488 KB Output is correct
58 Correct 3627 ms 1154448 KB Output is correct
59 Correct 3521 ms 1154608 KB Output is correct
60 Correct 3156 ms 1153796 KB Output is correct
61 Correct 2864 ms 1153820 KB Output is correct