제출 #1209639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209639		bangan	던전 (IOI21_dungeons)	C++20	0 / 100	1 ms	1096 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];

int nxt[N][K];
ll nxt_sum[N][K];

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--) {
		nxt[i][0] = w[i];
		nxt_sum[i][0] = s;
		for (int stp=1; stp<K; stp++) {
			int j = nxt[i][stp-1];
			if (j==n) {
				nxt[i][stp] = nxt[i][stp-1];
				nxt_sum[i][stp] = nxt_sum[i][stp-1];
			}
			else {
				nxt[i][stp] = nxt[j][stp-1];
				nxt_sum[i][stp] = nxt_sum[i][stp-1] + nxt_sum[j][stp-1];
			}
		}
	}

	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];
		}
	}
	if (pos!=n) {
		str += nxt_sum[pos][K-1];
	}

	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