Submission #1062182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062182		AmirAli_H1	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2951 ms	1390508 KiB

dungeons

// In the name of Allah

#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;

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

#define		endl					'\n'
#define		sep						' '
#define		F						first
#define		S						second
#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		pb						push_back
#define		Mp						make_pair

int n, q;
const int maxn = 4e5 + 7;
const int oo = 1e9 + 7;
const int maxlg = 24, maxlgx = 9;
int A1[maxn], A2[maxn];
ll val1[maxn], val2[maxn], sm[maxn];
int up[maxlgx][maxn][maxlg], mn[maxlgx][maxn][maxlg];
ll val[maxlgx][maxn][maxlg], P6[maxlgx];

void init(int Nx, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
	n = Nx;
	for (int i = 0; i < n; i++) {
		A1[i] = w[i]; A2[i] = l[i];
		val1[i] = s[i]; val2[i] = p[i];
	}
	A1[n] = n; val1[n] = 0;
	A2[n] = n; val2[n] = 0;
	
	sm[n] = 0;
	for (int i = n - 1; i >= 0; i--) {
		sm[i] = sm[A1[i]] + val1[i];
	}
	
	for (int R = 0; R < maxlgx; R++) {
		if (R == 0) P6[R] = 1;
		else P6[R] = P6[R - 1] * 6;
		for (int j = 0; j < maxlg; j++) {
			for (int i = 0; i <= n; i++) {
				if (j == 0) {
					if (P6[R] >= val1[i]) {
						up[R][i][0] = A1[i]; val[R][i][0] = val1[i];
						mn[R][i][0] = oo;
					}
					else {
						up[R][i][0] = A2[i]; val[R][i][0] = val2[i];
						mn[R][i][0] = val1[i];
					}
				}
				else {
					int k = up[R][i][j - 1];
					up[R][i][j] = up[R][k][j - 1];
					val[R][i][j] = val[R][i][j - 1] + val[R][k][j - 1];
					if (mn[R][k][j - 1] < oo) {
						mn[R][i][j] = min(mn[R][i][j - 1] + 0ll,
							max(0ll, mn[R][k][j - 1] - val[R][i][j - 1]));
					}
					else mn[R][i][j] = mn[R][i][j - 1];
				}
			}
		}
	}
}

ll simulate(int i, int w) {
	ll x = w;
	while (i != n && x < oo) {
		int R = upper_bound(P6, P6 + maxlgx, x) - P6 - 1;
		for (int j = maxlg - 1; j >= 0; j--) {
			if (x < mn[R][i][j]) {
				x += val[R][i][j]; i = up[R][i][j];
			}
		}
		if (x >= val1[i]) {
			x += val1[i]; i = A1[i];
		}
		else {
			x += val2[i]; i = A2[i];
		}
	}
	x += sm[i];
	return x;
}

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11