제출 #1050222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1050222		vjudge1	던전 (IOI21_dungeons)	C++17	0 / 100	544 ms	1881480 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][20];
	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<20;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[10];
int l[400100],p[400100],s[400100],w[400100],fin;
long long pws[20];
int llog(int x){
	for(int i=0;i<20;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<20;i++)
		pws[i]=pws[i-1]*8;
	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<10;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<10;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(10,llog(z));
		if(susss[K].thres(x,23)>z)
			return z+susss[K].strength(x,23);
		for(int i=23;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;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

dungeons.cpp: In function 'int llog(int)':
dungeons.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
   45 | }
      | ^
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:26:17: warning: array subscript 23 is above array bounds of 'level::dAtA [20]' [-Warray-bounds]
   26 |   return bj[n][k].thres;
      |          ~~~~~~~^
dungeons.cpp:23:17: warning: array subscript 23 is above array bounds of 'level::dAtA [20]' [-Warray-bounds]
   23 |   return bj[n][k].inc;
      |          ~~~~~~~^

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