제출 #612188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
612188		100jinseo	던전 (IOI21_dungeons)	C++17	37 / 100	7086 ms	1787452 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 = 1e9;

int nxt[400010][LOG1][LOG2];
ll sum[400010][LOG1][LOG2];
ll lmt[400010][LOG1][LOG2];
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[j][i][0] = -1;
				}
				else{
					nxt[j][i][0] = W[j];
					sum[j][i][0] = S[j];
					lmt[j][i][0] = INF;
				}
			}
			else{
				if (L[j]==n){
					nxt[j][i][0] = -1;
				}
				else{
					nxt[j][i][0] = L[j];
					sum[j][i][0] = P[j];
					lmt[j][i][0] = S[j];
				}
			}
		}
	}
	
	for (i=0; i<LOG1; i++){
		for (j=1; j<LOG2; j++){
			for (k=0; k<n; k++){
				if (nxt[k][i][j-1]==-1 || nxt[nxt[k][i][j-1]][i][j-1]==-1){
					nxt[k][i][j]=-1;
				}
				else{
					nxt[k][i][j] = nxt[nxt[k][i][j-1]][i][j-1];
					sum[k][i][j] = sum[k][i][j-1] + sum[nxt[k][i][j-1]][i][j-1];
					lmt[k][i][j] = min(lmt[k][i][j-1], lmt[nxt[k][i][j-1]][i][j-1] - sum[k][i][j-1]);
				}
			}
		}
	}

	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[x][lv][i]==-1) continue;
			if (str>=lmt[x][lv][i]) continue;
			str += sum[x][lv][i];
			x = nxt[x][lv][i];
		}

		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: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11