oj.uz

Submission #829460

# Submission time Handle Problem Language Result Execution time Memory
829460 2023-08-18T11:00:42 Z NothingXD Dungeons Game (IOI21_dungeons) C++17
100 / 100
 2713 ms 1904260 KB 
#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;

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

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 4e5 + 10;
const int lg = 20;
const int st = 5;
const int inf = 1e9;

int n, s[maxn], p[maxn], w[maxn], l[maxn];
int par[lg][lg][maxn];
int mn[lg][lg][maxn];
int sum[lg][lg][maxn];
ll val[maxn];

void init(int _n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) {
	n = _n;
	for (int i = 0; i < n; i++){
		s[i] = _s[i];
		p[i] = _p[i];
		w[i] = _w[i];
		l[i] = _l[i];
	}
	w[n] = l[n] = n;
	for (int i = 0; i < lg; i++){
		for (int k = 0; k <= n; k++){
			if (s[k] > (1 << (i+st))){
				sum[i][0][k] = p[k];
				mn[i][0][k] = s[k];
				par[i][0][k] = l[k];
			}
			else{
				sum[i][0][k] = s[k];
				mn[i][0][k] = inf;
				par[i][0][k] = w[k];
			}
		}
		for (int j = 1; j <= st; j++){
			for (int k = 0; k <= n; k++){
				int tmp = mn[i][j-1][par[i][j-1][k]];
				mn[i][j][k] = min(mn[i][j-1][k], tmp - sum[i][j-1][k]);
				mn[i][j][k] = max(mn[i][j][k], 0);
				par[i][j][k] = par[i][j-1][par[i][j-1][k]];
				sum[i][j][k] = min((int)1e7, sum[i][j-1][k] + sum[i][j-1][par[i][j-1][k]]);
			}
		}

		for (int k = 0; k <= n; k++){
				sum[i][0][k] = sum[i][st][k];
				mn[i][0][k] = mn[i][st][k];
				par[i][0][k] = par[i][st][k];
		}

		for (int j = 1; j < lg; j++){
			for (int k = 0; k <= n; k++){
				int tmp = mn[i][j-1][par[i][j-1][k]];
				mn[i][j][k] = min(mn[i][j-1][k], tmp - sum[i][j-1][k]);
				mn[i][j][k] = max(mn[i][j][k], 0);
				par[i][j][k] = par[i][j-1][par[i][j-1][k]];
				sum[i][j][k] = min((int)1e7, sum[i][j-1][k] + sum[i][j-1][par[i][j-1][k]]);
			}
		}
	}
	for (int i = n-1; ~i; i--){
		val[i] = val[w[i]] + s[i];
	}
	debug(1);
}

int lst = -1;

ll solve(int x, ll z){
//	debug(x, z);
	if (x == n) return z;
	if (z >= 1e7) return z + val[x];
	int ptr = 31 - __builtin_clz(z);
	ptr -= st;
	ptr = min(ptr, lg-1);
	if (ptr == lst) assert(0);
	lst = ptr;
	//debug(ptr);
	int v = x;
	ll cnt = z;
	for (int i = lg-1; ~i; i--){
	//	debug(i, v, mn[ptr][i][v], par[ptr][i][v], sum[ptr][i][v], cnt);
		if (sum[ptr][i][v] + cnt >= 1e7 || par[ptr][i][v] == n || mn[ptr][i][v] <= cnt) continue;
		cnt += sum[ptr][i][v];
		v = par[ptr][i][v];
	}
	//debug(v, cnt);
	int tmp = (1 << st);
//	debug(0, v, cnt);
	while(tmp--){
		if (cnt >= s[v]){
			cnt += s[v];
			v = w[v];
		}
		else{
			cnt += p[v];
			v = l[v];
		}
	}
	//debug(1, v, cnt);
	return solve(v, cnt);
}

long long simulate(int x, int z) {
	lst = -1;
	ll cnt = z;
	while(x != n && cnt < (1 << st)){
		if (cnt >= s[x]){
			cnt += s[x];
			x = w[x];
		}
		else{
			cnt += p[x];
			x = l[x];
		}
	}
	return solve(x, cnt);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8788 KB Output is correct
2 Correct 4 ms 8788 KB Output is correct
3 Correct 10 ms 18260 KB Output is correct
4 Correct 159 ms 246904 KB Output is correct
5 Correct 10 ms 18260 KB Output is correct
6 Correct 162 ms 246812 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13512 KB Output is correct
2 Correct 1428 ms 1904024 KB Output is correct
3 Correct 1231 ms 1904136 KB Output is correct
4 Correct 1290 ms 1904260 KB Output is correct
5 Correct 1335 ms 1904144 KB Output is correct
6 Correct 1235 ms 1904032 KB Output is correct
7 Correct 1321 ms 1904000 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13524 KB Output is correct
2 Correct 211 ms 247824 KB Output is correct
3 Correct 202 ms 248180 KB Output is correct
4 Correct 208 ms 247872 KB Output is correct
5 Correct 210 ms 247712 KB Output is correct
6 Correct 247 ms 247988 KB Output is correct
7 Correct 273 ms 247940 KB Output is correct
8 Correct 239 ms 247704 KB Output is correct
9 Correct 218 ms 247680 KB Output is correct
10 Correct 241 ms 247560 KB Output is correct
11 Correct 242 ms 247908 KB Output is correct
12 Correct 278 ms 247960 KB Output is correct
13 Correct 210 ms 248068 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13524 KB Output is correct
2 Correct 211 ms 247824 KB Output is correct
3 Correct 202 ms 248180 KB Output is correct
4 Correct 208 ms 247872 KB Output is correct
5 Correct 210 ms 247712 KB Output is correct
6 Correct 247 ms 247988 KB Output is correct
7 Correct 273 ms 247940 KB Output is correct
8 Correct 239 ms 247704 KB Output is correct
9 Correct 218 ms 247680 KB Output is correct
10 Correct 241 ms 247560 KB Output is correct
11 Correct 242 ms 247908 KB Output is correct
12 Correct 278 ms 247960 KB Output is correct
13 Correct 210 ms 248068 KB Output is correct
14 Correct 7 ms 13524 KB Output is correct
15 Correct 215 ms 248140 KB Output is correct
16 Correct 207 ms 248320 KB Output is correct
17 Correct 229 ms 247816 KB Output is correct
18 Correct 227 ms 247864 KB Output is correct
19 Correct 247 ms 247976 KB Output is correct
20 Correct 250 ms 247632 KB Output is correct
21 Correct 235 ms 247760 KB Output is correct
22 Correct 207 ms 247824 KB Output is correct
23 Correct 251 ms 247868 KB Output is correct
24 Correct 324 ms 248008 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13524 KB Output is correct
2 Correct 211 ms 247824 KB Output is correct
3 Correct 202 ms 248180 KB Output is correct
4 Correct 208 ms 247872 KB Output is correct
5 Correct 210 ms 247712 KB Output is correct
6 Correct 247 ms 247988 KB Output is correct
7 Correct 273 ms 247940 KB Output is correct
8 Correct 239 ms 247704 KB Output is correct
9 Correct 218 ms 247680 KB Output is correct
10 Correct 241 ms 247560 KB Output is correct
11 Correct 242 ms 247908 KB Output is correct
12 Correct 278 ms 247960 KB Output is correct
13 Correct 210 ms 248068 KB Output is correct
14 Correct 7 ms 13524 KB Output is correct
15 Correct 215 ms 248140 KB Output is correct
16 Correct 207 ms 248320 KB Output is correct
17 Correct 229 ms 247816 KB Output is correct
18 Correct 227 ms 247864 KB Output is correct
19 Correct 247 ms 247976 KB Output is correct
20 Correct 250 ms 247632 KB Output is correct
21 Correct 235 ms 247760 KB Output is correct
22 Correct 207 ms 247824 KB Output is correct
23 Correct 251 ms 247868 KB Output is correct
24 Correct 324 ms 248008 KB Output is correct
25 Correct 184 ms 247188 KB Output is correct
26 Correct 213 ms 248344 KB Output is correct
27 Correct 204 ms 247740 KB Output is correct
28 Correct 204 ms 247776 KB Output is correct
29 Correct 221 ms 248224 KB Output is correct
30 Correct 247 ms 248028 KB Output is correct
31 Correct 261 ms 247632 KB Output is correct
32 Correct 403 ms 247820 KB Output is correct
33 Correct 354 ms 247888 KB Output is correct
34 Correct 1210 ms 247652 KB Output is correct
35 Correct 477 ms 247800 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13512 KB Output is correct
2 Correct 1428 ms 1904024 KB Output is correct
3 Correct 1231 ms 1904136 KB Output is correct
4 Correct 1290 ms 1904260 KB Output is correct
5 Correct 1335 ms 1904144 KB Output is correct
6 Correct 1235 ms 1904032 KB Output is correct
7 Correct 1321 ms 1904000 KB Output is correct
8 Correct 7 ms 13524 KB Output is correct
9 Correct 211 ms 247824 KB Output is correct
10 Correct 202 ms 248180 KB Output is correct
11 Correct 208 ms 247872 KB Output is correct
12 Correct 210 ms 247712 KB Output is correct
13 Correct 247 ms 247988 KB Output is correct
14 Correct 273 ms 247940 KB Output is correct
15 Correct 239 ms 247704 KB Output is correct
16 Correct 218 ms 247680 KB Output is correct
17 Correct 241 ms 247560 KB Output is correct
18 Correct 242 ms 247908 KB Output is correct
19 Correct 278 ms 247960 KB Output is correct
20 Correct 210 ms 248068 KB Output is correct
21 Correct 7 ms 13524 KB Output is correct
22 Correct 215 ms 248140 KB Output is correct
23 Correct 207 ms 248320 KB Output is correct
24 Correct 229 ms 247816 KB Output is correct
25 Correct 227 ms 247864 KB Output is correct
26 Correct 247 ms 247976 KB Output is correct
27 Correct 250 ms 247632 KB Output is correct
28 Correct 235 ms 247760 KB Output is correct
29 Correct 207 ms 247824 KB Output is correct
30 Correct 251 ms 247868 KB Output is correct
31 Correct 324 ms 248008 KB Output is correct
32 Correct 184 ms 247188 KB Output is correct
33 Correct 213 ms 248344 KB Output is correct
34 Correct 204 ms 247740 KB Output is correct
35 Correct 204 ms 247776 KB Output is correct
36 Correct 221 ms 248224 KB Output is correct
37 Correct 247 ms 248028 KB Output is correct
38 Correct 261 ms 247632 KB Output is correct
39 Correct 403 ms 247820 KB Output is correct
40 Correct 354 ms 247888 KB Output is correct
41 Correct 1210 ms 247652 KB Output is correct
42 Correct 477 ms 247800 KB Output is correct
43 Correct 4 ms 8788 KB Output is correct
44 Correct 8 ms 13528 KB Output is correct
45 Correct 1577 ms 1902944 KB Output is correct
46 Correct 1304 ms 1902696 KB Output is correct
47 Correct 1318 ms 1902772 KB Output is correct
48 Correct 1431 ms 1902644 KB Output is correct
49 Correct 1661 ms 1902592 KB Output is correct
50 Correct 1317 ms 1902532 KB Output is correct
51 Correct 1254 ms 1902408 KB Output is correct
52 Correct 1289 ms 1902288 KB Output is correct
53 Correct 1982 ms 1902056 KB Output is correct
54 Correct 1425 ms 1902104 KB Output is correct
55 Correct 2460 ms 1902024 KB Output is correct
56 Correct 2133 ms 1901968 KB Output is correct
57 Correct 2261 ms 1902028 KB Output is correct
58 Correct 2488 ms 1901628 KB Output is correct
59 Correct 2713 ms 1901624 KB Output is correct
60 Correct 2126 ms 1901820 KB Output is correct
61 Correct 1894 ms 1901644 KB Output is correct