제출 #645172

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

dungeons

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

typedef long long ll;

#define maxn 400001
#define lgn 8
#define base 8
#define INF 1023456789123456789

int n,to[maxn][lgn][lgn+1];
ll gain[maxn][lgn][lgn+1],mn[maxn][lgn][lgn+1],pwr[lgn+2];
vector<int> s,w;

void init(int _n,vector<int> _s,vector<int> p,vector<int> _w,vector<int> l){
	pwr[0]=1;
	for(int i=1;i<=lgn+1;++i)pwr[i]=pwr[i-1]*base;
	n=_n;s=_s;w=_w;
	for(int k=0;k<=lgn;++k){//win if <base^k, lose if >=base^k
		for(int i=0;i<n;++i){
			to[i][0][k]=(s[i]<pwr[k])?w[i]:l[i];
			gain[i][0][k]=(s[i]<pwr[k])?s[i]:p[i];
			mn[i][0][k]=(s[i]<pwr[k])?INF:s[i];
		}
		to[n][0][k]=n;
		gain[n][0][k]=0;
		mn[n][0][k]=INF;
		for(int j=1;j<lgn;++j){
			for(int i=0;i<=n;++i){
				int cur=i;
				mn[i][j][k]=INF;
				for(int b=0;b<base;++b){
					to[i][j][k]=to[cur][j-1][k];
					mn[i][j][k]=min(mn[i][j][k],mn[cur][j-1][k]-gain[i][j][k]);
					gain[i][j][k]+=gain[cur][j-1][k];
					cur=to[cur][j-1][k];
				}
			}
		}
	}
}

ll simulate(int x,int z){
	ll str=z;
	int pos=x;
	while(pos!=n){
		int k=0;
		while(pwr[k+1]<=str)++k;
		if(k>lgn){
			int cur=pos;
			for(int b=0;b<base-1;++b){
				str+=gain[cur][lgn-1][lgn];
				cur=to[pos][lgn-1][lgn];
			}
			return str;
		}
		for(int j=lgn-1;j>=0;--j){
			for(int b=0;b<base-1;++b){
				if(str<mn[pos][j][k]){
					str+=gain[pos][j][k];
					pos=to[pos][j][k];
				}
			}
		}
		if(pos!=n){
			str+=s[pos];
			pos=w[pos];
		}
	}
	return str;
}

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