제출 #618035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
618035		Soumya1	던전 (IOI21_dungeons)	C++17	89 / 100	7120 ms	1749752 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 400000;
const int lg2 = 20;
const int lg5 = 11;
const long long inf = 1e18;
int to[lg5][lg2][mxN];
long long lim[lg5][lg2][mxN];
long long add[lg5][lg2][mxN];
int pw[lg5];
int n;
vector<int> s, p, w, l;
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
	n = _n, s = _s, p = _p, w = _w, l = _l;
	pw[0] = 1;
	for (int i = 1; i < lg5; i++) pw[i] = pw[i - 1] * 5;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < lg5; j++) {
			if (pw[j] >= s[i]) {
				to[j][0][i] = w[i];
				add[j][0][i] = s[i];
				lim[j][0][i] = inf;
			} else {
				to[j][0][i] = l[i];
				add[j][0][i] = p[i];
				lim[j][0][i] = s[i];
			}
		}
	}
	for (int i = 0; i < lg5; i++) {
		for (int j = 1; j < lg2; j++) {
			for (int k = 0; k < n; k++) {
				if (to[i][j - 1][k] == n) {
					to[i][j][k] = n;
					continue;
				}
				to[i][j][k] = to[i][j - 1][to[i][j - 1][k]];
				add[i][j][k] = add[i][j - 1][k] + add[i][j - 1][to[i][j - 1][k]];
				if (lim[i][j - 1][to[i][j - 1][k]] == inf) lim[i][j][k] = lim[i][j - 1][k];
				else if (add[i][j - 1][k] > lim[i][j - 1][to[i][j - 1][k]]) lim[i][j][k] = 0;
				else lim[i][j][k] = min(lim[i][j - 1][k], lim[i][j - 1][to[i][j - 1][k]] - add[i][j - 1][k]);
			}
		}
	}
	return;
}

long long simulate(int x, int _z) {
	long long z = _z;
	while (x != n) {
		int c = 0;
		while (c + 1 < lg5 && pw[c + 1] <= z) c++;
		for (int j = lg2 - 1; j >= 0; j--) {
			if (z >= lim[c][j][x]) continue;
			if (to[c][j][x] == n) continue;
			z += add[c][j][x];
			x = to[c][j][x];
		}
		if (x == n) break;
		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: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 0 / 11