제출 #774867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
774867		SanguineChameleon	던전 (IOI21_dungeons)	C++17	36 / 100	7054 ms	145296 KiB

dungeons

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

const int maxN = 4e5 + 20;
const int maxT = 10;
const int maxK = 30;
pair<int, long long> jump[maxT][maxN][maxK];
int S[maxN];
int P[maxN];
int W[maxN];
int L[maxN];
vector<int> S_vals;
int N, T;
bool sub34;

void init(int _N, vector<int> _S, vector<int> _P, vector<int> _W, vector<int> _L) {
	N = _N;
	for (int i = 0; i < N; i++) {
		S[i] = _S[i];
		P[i] = _P[i];
		W[i] = _W[i];
		L[i] = _L[i];
	}
	S_vals = _S;
	sort(S_vals.begin(), S_vals.end());
	S_vals.erase(unique(S_vals.begin(), S_vals.end()), S_vals.end());
	T = S_vals.size();
	sub34 = (T <= 5);
	if (sub34) {
		for (int t = 0; t <= T; t++) {
			for (int i = 0; i < N; i++) {
				if (t == T || S[i] < S_vals[t]) {
					jump[t][i][0] = make_pair(W[i], S[i]);
				}
				else {
					jump[t][i][0] = make_pair(L[i], P[i]);
				}
			}
			jump[t][N][0] = make_pair(N, 0);
			for (int k = 1; k < maxK; k++) {
				jump[t][N][k] = make_pair(N, 0);
				for (int i = 0; i < N; i++) {
					int nxt = jump[t][i][k - 1].first;
					jump[t][i][k] = make_pair(jump[t][nxt][k - 1].first, jump[t][i][k - 1].second + jump[t][nxt][k - 1].second);
				}
			}
		}
	}
	return;
}

long long simulate(int X, int _Z) {
	if (sub34) {
		long long Z = _Z;
		while (X != N) {
			int t = upper_bound(S_vals.begin(), S_vals.end(), Z) - S_vals.begin();
			for (int k = maxK - 1; k >= 0; k--) {
				if (jump[t][X][k].first != N && (t == T || Z + jump[t][X][k].second < S_vals[t])) {
					Z += jump[t][X][k].second;
					X = jump[t][X][k].first;
				}
			}
			Z += jump[t][X][0].second;
			X = jump[t][X][0].first;
		}
		return Z;
	}
	else {
		int Z = _Z;
		while (X != N) {
			if (Z >= S[X]) {
				Z += S[X];
				X = W[X];
			}
			else {
				Z += P[X];
				X = L[X];
			}
		}
		return Z;
	}
}

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