제출 #612203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
612203		100jinseo	던전 (IOI21_dungeons)	C++17	100 / 100	3720 ms	1741936 KiB

dungeons

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

const int LOG1 = 9; // 8^i를 기준
const int LOG2 = 25;
const long long INF = 1e18;

int nxt[LOG1][LOG2][400010];
ll sum[LOG1][LOG2][400010];
ll lmt[LOG1][LOG2][400010];
ll ex[LOG1];

int N;
vector <int> S, P, W, L;

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	N=n, S=s, P=p, W=w, L=l;

	int i, j, k;
	ex[0] = 1;
	for (i=1; i<LOG1; i++){
		ex[i] = ex[i-1]*8;
	}

	for (i=0; i<LOG1; i++){
		for (j=0; j<n; j++){
			if (ex[i] >= S[j]){
				if (W[j]==n){
					nxt[i][0][j] = -1;
				}
				else{
					nxt[i][0][j] = W[j];
					sum[i][0][j] = S[j];
					lmt[i][0][j] = INF;
				}
			}
			else{
				if (L[j]==n){
					nxt[i][0][j] = -1;
				}
				else{
					nxt[i][0][j] = L[j];
					sum[i][0][j] = P[j];
					lmt[i][0][j] = S[j];
				}
			}
		}
	}

	for (i=0; i<LOG1; i++){
		for (j=1; j<LOG2; j++){
			for (k=0; k<n; k++){
				if (nxt[i][j-1][k]==-1 || nxt[i][j-1][nxt[i][j-1][k]]==-1){
					nxt[i][j][k]=-1;
				}
				else{
					nxt[i][j][k] = nxt[i][j-1][nxt[i][j-1][k]];
					sum[i][j][k] = sum[i][j-1][k] + sum[i][j-1][nxt[i][j-1][k]];
					lmt[i][j][k] = min(lmt[i][j-1][k], lmt[i][j-1][nxt[i][j-1][k]] - sum[i][j-1][k]);
				}
			}
		}
	}

	return;
}

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

	int i, lv=0;

	while(x!=N){

		while (lv+1<LOG1 && str>=ex[lv+1]){
			lv++;
		}

		for (i=LOG2-1; i>=0; i--){
			if (nxt[lv][i][x]==-1) continue;
			if (str>=lmt[lv][i][x]) continue;
			str += sum[lv][i][x];
			x = nxt[lv][i][x];
		}

		if (str>=S[x]){
			str += S[x];
			x = W[x];
		}
		else{
			str += P[x];
			x = L[x];
		}

	}

	return str;
}

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