Submission #1209622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209622		bangan	Dungeons Game (IOI21_dungeons)	C++20	0 / 100	1 ms	836 KiB

dungeons

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

const int N = 4e5 + 8;
const int K = 25;

int n;
int s[N];
int p[N];
int w[N];
int l[N];

int nxt[N][K];
ll mx[N][K];
ll sum[N][K];

void init(int n_in, std::vector<int> s_in, std::vector<int> p_in, std::vector<int> w_in, std::vector<int> l_in) {
	n = n_in;
	for (int i=0; i<n; i++) {
		s[i] = s_in[i];
		p[i] = p_in[i];
		w[i] = w_in[i];
		l[i] = l_in[i];
	}

	for (int i=n-1; i>=0; i--) {
		nxt[i][0] = w[i];
		mx[i][0] = s[i];
		sum[i][0] = s[i];
	
		for (int stp=1; stp<K; stp++) {
			int j = nxt[i][stp-1];
			if (j == n) {
				nxt[i][stp] = nxt[i][stp-1];
				mx[i][stp] = mx[i][stp-1];
				sum[i][stp] = sum[i][stp-1];
			}
			else {
				nxt[i][stp] = nxt[j][stp-1];
				mx[i][stp] = max(mx[i][stp-1], mx[j][stp-1] + sum[i][stp-1]);
				sum[i][stp] = sum[i][stp-1] + sum[j][stp-1];
			}
		}
	}
}

long long simulate(int x, int z) {
	int pos = x;
	ll str = z;

	while (pos != n) {
		for (int i=K-1; i>=0 && pos!=n; i--) if (mx[pos][i] <= str) {
			str += sum[pos][i];
			pos = nxt[pos][i];
		}
		if (pos != n) {
			str += s[pos];
			pos = l[pos];
		}
	}

	return str;
}

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