Submission #829393

#	Time	Username	Problem	Language	Result	Execution time	Memory
829393		ymm	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7073 ms	254652 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
using namespace std;

const int N = 400'010;
const int lg = 30;
int nxt[lg][N];
ll add[lg][N];
ll mn[lg][N];
vector<int> s, p, w, l;
int n;

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	::n = n;
	::s = s;
	::p = p;
	::w = w;
	::l = l;
	Loop (i,0,n) {
		nxt[0][i] = w[i];
		add[0][i] = s[i];
		mn[0][i] = s[i];
	}
	nxt[0][n] = n;
	Loop (j,0,lg-1) Loop (i,0,n+1) {
		nxt[j+1][i] = nxt[j][nxt[j][i]];
		add[j+1][i] = add[j][i] + add[j][nxt[j][i]];
		mn[j+1][i] = max(mn[j][i], mn[j][nxt[j][i]] - add[j][i]);
	}
}

long long simulate(int x, int z) {
	ll val = z;
	for (;;) {
		LoopR (i,0,lg) {
			if (mn[i][x] <= val) {
				val += add[i][x];
				x = nxt[i][x];
			}
		}
		if (x == n)
			break;
		assert(val < s[x]);
		val += p[x];
		x = l[x];
	}
	return val;
}

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