Submission #1048903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048903		AmirAli_H1	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	255 ms	244816 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; bool ok = 1;
const int maxn = 4e5 + 7;
const int maxlg = 20, maxlgx = 25;
const ll oo = 1e18 + 4;
ll val1[maxn], val2[maxn], A1[maxn], A2[maxn];
ll sm[maxn], valx[maxn];
ll mx[maxn][maxlg]; int up[maxn][maxlg];
ll Ax[maxn][maxlgx]; int upx[maxn][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];
		if (val1[i] != val1[0]) ok = 0;
	}
	A1[n] = n; val1[n] = 0;
	
	sm[n] = 0; valx[n] = 0;
	for (int i = n - 1; i >= 0; i--) {
		int j = A1[i];
		sm[i] = sm[j] + val1[i];
		valx[i] = val1[i] + sm[i];
	}
	
	for (int i = n; i >= 0; i--) {
		up[i][0] = A1[i]; mx[i][0] = valx[i];
		for (int j = 1; j < maxlg; j++) {
			int r = up[i][j - 1];
			up[i][j] = up[r][j - 1]; mx[i][j] = max(mx[i][j - 1], mx[r][j - 1]);
		}
	}
	
	for (int j = 0; j < maxlgx; j++) {
		for (int i = 0; i < n; i++) {
			if (j == 0) {
				upx[i][j] = A2[i]; Ax[i][j] = val2[i];
			}
			else {
				int r = upx[i][j - 1];
				upx[i][j] = upx[r][j - 1];
				Ax[i][j] = min(oo, Ax[i][j - 1] + Ax[r][j - 1]);
			}
		}
	}
}

ll cal(int i, ll x) {
	if (i == n) return x;
	if (x < val1[i]) return cal(A2[i], x + val2[i]);
	
	ll R = x + sm[i];
	for (int j = maxlg - 1; j >= 0; j--) {
		if (mx[i][j] <= R) {
			x += sm[i]; x -= sm[up[i][j]];
			i = up[i][j];
		}
	}
	return cal(i, x);
}

ll calx(int i, ll x) {
	if (i == n) return x;
	if (x >= val1[i]) return x + sm[i];
	
	for (int j = maxlgx - 1; j >= 0; j--) {
		if (x + Ax[i][j] < val1[i]) {
			x += Ax[i][j]; i = upx[i][j];
		}
	}
	x += Ax[i][0]; i = upx[i][0];
	return x + sm[i];
}

ll simulate(int x, int z) {
	if (!ok) return cal(x, z);
	else return calx(x, z);
}

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