oj.uz

Submission #1048773

# Submission time Handle Problem Language Result Execution time Memory
1048773 2024-08-08T09:30:13 Z DorostWef Dungeons Game (IOI21_dungeons) C++17
37 / 100
 1514 ms 1161576 KB 
#include "dungeons.h"
#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

using namespace std;

typedef long long ll;
#define F first
#define S second
#define mk make_pair
typedef pair <int, int> pii;
const int N = 400023, LG = 24, L2 = 10, K = 4;
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 = 1e8;
				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;
					int wef = nx[w][y][j - 1].S.F - nx[w][i][j].S.S;
					if (wef < 0)
						wef = -1;
					nx[w][i][j].S.F = min (nx[w][i][j].S.F, wef);
					nx[w][i][j].S.S = min ({(int)1e9, 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) {
	if (z <= nx[w][x][L2 - 1].S.F) {
		z += nx[w][x][L2 - 1].S.S;
		x = nx[w][x][L2 - 1].F;
	}
	for (int i = L2 - 2; 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;
	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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 57688 KB Output is correct
2 Correct 5 ms 57948 KB Output is correct
3 Correct 8 ms 64088 KB Output is correct
4 Correct 119 ms 180696 KB Output is correct
5 Correct 9 ms 64092 KB Output is correct
6 Correct 131 ms 181388 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 57948 KB Output is correct
2 Correct 1321 ms 1160136 KB Output is correct
3 Correct 1225 ms 1160280 KB Output is correct
4 Correct 1271 ms 1161532 KB Output is correct
5 Correct 1514 ms 1161576 KB Output is correct
6 Correct 1339 ms 1160336 KB Output is correct
7 Correct 1210 ms 1158464 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 57948 KB Output is correct
2 Correct 193 ms 182992 KB Output is correct
3 Correct 124 ms 182080 KB Output is correct
4 Correct 126 ms 181460 KB Output is correct
5 Correct 133 ms 180372 KB Output is correct
6 Correct 166 ms 180560 KB Output is correct
7 Incorrect 156 ms 180412 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 57948 KB Output is correct
2 Correct 193 ms 182992 KB Output is correct
3 Correct 124 ms 182080 KB Output is correct
4 Correct 126 ms 181460 KB Output is correct
5 Correct 133 ms 180372 KB Output is correct
6 Correct 166 ms 180560 KB Output is correct
7 Incorrect 156 ms 180412 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 57948 KB Output is correct
2 Correct 193 ms 182992 KB Output is correct
3 Correct 124 ms 182080 KB Output is correct
4 Correct 126 ms 181460 KB Output is correct
5 Correct 133 ms 180372 KB Output is correct
6 Correct 166 ms 180560 KB Output is correct
7 Incorrect 156 ms 180412 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 57948 KB Output is correct
2 Correct 1321 ms 1160136 KB Output is correct
3 Correct 1225 ms 1160280 KB Output is correct
4 Correct 1271 ms 1161532 KB Output is correct
5 Correct 1514 ms 1161576 KB Output is correct
6 Correct 1339 ms 1160336 KB Output is correct
7 Correct 1210 ms 1158464 KB Output is correct
8 Correct 6 ms 57948 KB Output is correct
9 Correct 193 ms 182992 KB Output is correct
10 Correct 124 ms 182080 KB Output is correct
11 Correct 126 ms 181460 KB Output is correct
12 Correct 133 ms 180372 KB Output is correct
13 Correct 166 ms 180560 KB Output is correct
14 Incorrect 156 ms 180412 KB Output isn't correct
15 Halted 0 ms 0 KB -