제출 #1049562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049562		vjudge1	던전 (IOI21_dungeons)	C++17	0 / 100	18 ms	50828 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
struct level {
	int bj[50100][25];
	long long inc[50100][25];
	int strength(int n,int k){
		return inc[n][k];
	}
	int dungeon(int n,int k){
		return bj[n][k];
	}
	void setdungeon(int n,int go,int add){
		inc[n][0]=add;
		bj[n][0]=go;
	}
	void preproc(int n){
		for(int j=1;j<25;j++)
			for(int i=0;i<=n;i++)
				bj[i][j]=bj[bj[i][j-1]][j-1],
				inc[i][j]=inc[i][j-1]+inc[bj[i][j-1]][j-1];
	}
} thgs[6];
map<long long,int>mp;
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l) {
	mp[1e18]=6;
	for(int i=0;i<n;i++)
		mp[s[i]];
	int CC=0;
	for(auto&[i,j]:mp)
		j=CC++;
	for(int i=0;i<n;i++)
		for(int j=0;j<6;j++)
			if(j<=mp[s[i]])
				thgs[j].setdungeon(i,l[i],p[i]);
			else thgs[j].setdungeon(i,w[i],s[i]);
	for(int i=0;i<6;i++)
		thgs[i].setdungeon(n,n,0),
		thgs[i].preproc(n);
}

long long simulate(int x, int z) {
	while(1){
		auto[nxtreq,curlev]=*mp.upper_bound(z);
		if(thgs[curlev].strength(x,24)+z<nxtreq)
			return z+thgs[curlev].strength(x,24);
		for(int i=24;i--;)
			if(thgs[curlev].strength(x,i)+z<nxtreq)
				z+=thgs[curlev].strength(x,i),
				x=thgs[curlev].dungeon(x,i);
		z+=thgs[curlev].strength(x,0);
		x=thgs[curlev].dungeon(x,0);
	}
}

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