Submission #1050254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050254		vjudge1	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2173 ms	2061108 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
struct level {
	private:
	struct dAtA{
		int to;
		long long inc,thres;
		dAtA(int go,int add,long long T){
			to=go,inc=add,thres=T;
		}
		dAtA(){
			to=0,inc=0,thres=0;
		}
		dAtA(dAtA a,dAtA b){
			to=b.to;
			inc=a.inc+b.inc;
			thres=min(1ll*a.thres,b.thres-a.inc);
		}
	} bj[400100][24];
	public:
	long long strength(int n,int k){
		return bj[n][k].inc;
	}
	long long thres(int n,int k){
		return bj[n][k].thres;
	}
	int dungeon(int n,int k){
		return bj[n][k].to;
	}
	void setdungeon(int n,int go,int add,long long T){
		bj[n][0]=dAtA(go,add,T);
	}
	void preproc(int n){
		for(int j=1;j<24;j++) for(int i=0;i<=n;i++)
			bj[i][j]=dAtA(bj[i][j-1],bj[bj[i][j-1].to][j-1]);
	}
} susss[9];
int l[400100],p[400100],s[400100],w[400100],fin;
long long pws[24];
int llog(int x){
	for(int i=0;i<24;i++)
		if(pws[i+1]>x)
			return i;
}
void init(int n,vector<int> S,vector<int> P,vector<int> W,vector<int> L) {
	fin=n;
	pws[0]=1;
	for(int i=1;i<24;i++)
		pws[i]=pws[i-1]*10;
	for(int i=0;i<n;i++) l[i]=L[i],p[i]=P[i],s[i]=S[i],w[i]=W[i];
	for(int j=0;j<9;j++)
		for(int i=0;i<n;i++) {
			if(s[i]<=pws[j])
				susss[j].setdungeon(i,w[i],s[i],1e18);
			else susss[j].setdungeon(i,l[i],p[i],s[i]);
		}
	for(int i=0;i<9;i++)
		susss[i].setdungeon(n,n,0,1e18),
		susss[i].preproc(n);
}

long long simulate(int x, int Z) {
	long long z=Z;
	while(1){
		int K=min(8,llog(z));
		for(int i=24;i--;)
			if(susss[K].thres(x,i)>z)
				z+=susss[K].strength(x,i),
				x=susss[K].dungeon(x,i);
		if(x==fin) return z;
		int k=s[x];
		if(k<=z)
			x=w[x],z+=k;
		else x=l[x],z+=p[x];
		if(x==fin) return z;
	}
}

Compilation message (stderr)

dungeons.cpp: In function 'int llog(int)':
dungeons.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
   45 | }
      | ^

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