Submission #1209667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209667		bangan	Dungeons Game (IOI21_dungeons)	C++20	0 / 100	1 ms	840 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;
int p[N];
int w[N];
int l[N];

ll sum_win[N];

int prv[N][K];
ll prv_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;
	s = s_in[0];
	for (int i=0; i<n; i++) {
		p[i] = p_in[i];
		w[i] = w_in[i];
		l[i] = l_in[i];
	}

	for (int i=n-1; i>= 0; i--) {
		sum_win[i] = s + sum_win[w[i]];
	}

	for (int i=0; i<n; i++) {
		prv[i][0] = l[i];
		prv_sum[i][0] = p[i];
	}
	for (int stp=1; stp<K; stp++) {
		for (int i=0; i<n; i++) {
			int j = prv[i][stp-1];
			if (j==n) {
				prv[i][stp] = prv[i][stp-1];
				prv_sum[i][stp] = prv_sum[i][stp-1];
			}
			else {
				prv[i][stp] = prv[j][stp-1];
				prv_sum[i][stp] = prv_sum[i][stp-1] + prv_sum[j][stp-1];
			}
		}
	}
}

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

	for (int i=K-1; i>=0 && pos!=n; i--) {
		if (str + prv_sum[pos][i] <= s) {
			str += prv_sum[pos][i];
			pos = prv[pos][i];
		}
	}
	// std::cout << "last lose = \t" << pos << '\n';
	// std::cout << "cur str = \t" << str << '\n';

	if (pos!=n) {
		str += sum_win[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