oj.uz

Submission #1048706

# Submission time Handle Problem Language Result Execution time Memory
1048706 2024-08-08T09:11:26 Z DorostWef Dungeons Game (IOI21_dungeons) C++17
13 / 100
 7000 ms 297036 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define F first
#define S second
#define mk make_pair
typedef pair <ll, ll> pii;
const int N = 400023, LG = 24, L2 = 9, K = 5;
int s[N], p[N], o[N], l[N], n;
long long m[N], a[N];
pair <int, pii> nx[LG][N][L2];
const ll INF = 1e18;

void init(int nn, std::vector<int> ss, std::vector<int> pp, std::vector<int> ww, std::vector<int> ll) {
	n = nn;
	for (int i = 0; i < n; i++) {
		s[i] = ss[i];
		p[i] = pp[i];
		o[i] = ww[i];
		l[i] = ll[i];
	}
	m[n] = 0;
	a[n] = 0;
	l[n] = n;
	o[n] = n;
	s[n] = 0;
	for (int i = n - 1; i >= 0; i--) {
		a[i] = a[o[i]] + s[i];
		m[i] = max((long long)s[i], m[o[i]] - s[i]);
	}
	for (int w = 0; w < LG; w++) {
		for (int i = 0; i <= n; i++) {
			if (i < n && s[i] <= (1 << w)) {
				nx[w][i][0].F = o[i];
				nx[w][i][0].S.F = INF;
				nx[w][i][0].S.S = s[i];
			} else {
				nx[w][i][0].F = l[i];
				nx[w][i][0].S.F = s[i] - 1;
				nx[w][i][0].S.S = p[i];
			}
		}
		for (int j = 1; j < L2; j++) {
			for (int i = 0; i <= n; i++) {
				nx[w][i][j].S.S = nx[w][i][j - 1].S.S;
				nx[w][i][j].S.F = nx[w][i][j - 1].S.F;
				nx[w][i][j].F = nx[w][i][j - 1].F;
				for (int k = 0; k < K; k++) {
					int y = nx[w][i][j].F;
					nx[w][i][j].F = nx[w][y][j - 1].F;
					nx[w][i][j].S.F = min (nx[w][i][j].S.F, nx[w][y][j - 1].S.F - nx[w][i][j].S.S);
					nx[w][i][j].S.S = nx[w][i][j].S.S + nx[w][y][j - 1].S.S;
				}
			}
		}
	}
	return;
}

pair <int, long long> findd (int w, int x, ll z) {
	for (int i = L2 - 1; i >= 0; i--) {
		for (int k = 0; k < K; k++) {
			if (z <= nx[w][x][i].S.F) {
				z += nx[w][x][i].S.S;
				x = nx[w][x][i].F;
			}
		}
	}
	return {x, z};
}

ll ans (int x, ll z) {
	if (z >= m[x])
		return z + a[x];
	int l = 0;
	while ((1 << l) < s[x])
		l++;
	pair <int, ll> pp = findd (l, x, z);
	x = pp.F;
	z = pp.S;
	if (z >= s[x]) {
		z += s[x];
		x = o[x];
	}
	return ans (x, z);
}

long long simulate(int x, int z) {
	pair <int, ll> pp = findd (0, x, z);
	x = pp.F;
	z = pp.S;
	ll w = ans (x, z);
	return w;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 57688 KB Output is correct
2 Correct 5 ms 57692 KB Output is correct
3 Correct 9 ms 68300 KB Output is correct
4 Correct 186 ms 296348 KB Output is correct
5 Incorrect 9 ms 68188 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7066 ms 68188 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 68188 KB Output is correct
2 Correct 251 ms 295472 KB Output is correct
3 Correct 188 ms 295504 KB Output is correct
4 Correct 188 ms 294996 KB Output is correct
5 Correct 188 ms 295508 KB Output is correct
6 Correct 217 ms 295504 KB Output is correct
7 Correct 229 ms 295508 KB Output is correct
8 Correct 213 ms 295412 KB Output is correct
9 Correct 201 ms 295504 KB Output is correct
10 Correct 190 ms 295652 KB Output is correct
11 Correct 355 ms 294916 KB Output is correct
12 Correct 455 ms 295644 KB Output is correct
13 Correct 270 ms 294916 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 68188 KB Output is correct
2 Correct 251 ms 295472 KB Output is correct
3 Correct 188 ms 295504 KB Output is correct
4 Correct 188 ms 294996 KB Output is correct
5 Correct 188 ms 295508 KB Output is correct
6 Correct 217 ms 295504 KB Output is correct
7 Correct 229 ms 295508 KB Output is correct
8 Correct 213 ms 295412 KB Output is correct
9 Correct 201 ms 295504 KB Output is correct
10 Correct 190 ms 295652 KB Output is correct
11 Correct 355 ms 294916 KB Output is correct
12 Correct 455 ms 295644 KB Output is correct
13 Correct 270 ms 294916 KB Output is correct
14 Correct 8 ms 68364 KB Output is correct
15 Execution timed out 7012 ms 297036 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 68188 KB Output is correct
2 Correct 251 ms 295472 KB Output is correct
3 Correct 188 ms 295504 KB Output is correct
4 Correct 188 ms 294996 KB Output is correct
5 Correct 188 ms 295508 KB Output is correct
6 Correct 217 ms 295504 KB Output is correct
7 Correct 229 ms 295508 KB Output is correct
8 Correct 213 ms 295412 KB Output is correct
9 Correct 201 ms 295504 KB Output is correct
10 Correct 190 ms 295652 KB Output is correct
11 Correct 355 ms 294916 KB Output is correct
12 Correct 455 ms 295644 KB Output is correct
13 Correct 270 ms 294916 KB Output is correct
14 Correct 8 ms 68364 KB Output is correct
15 Execution timed out 7012 ms 297036 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7066 ms 68188 KB Time limit exceeded
2 Halted 0 ms 0 KB -