제출 #1049579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049579		vjudge1	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	150 ms	187728 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
struct level {
	private:
	int bj[200100][25],mx[200100][25];
	long long inc[200100][25];
	public:
	long long strength(int n,int k){
		return inc[n][k];
	}
	int strongest(int n,int k){
		return mx[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;
		mx[n][0]=add;
	}
	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],
				mx[i][j]=max(mx[i][j-1],mx[bj[i][j-1]][j-1]);
	}
} sus;
map<long long,int>mp;
int l[200100];
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> L) {
	for(int i=0;i<n;i++)
		mp[s[i]];
	int CC=0;
	for(auto&[i,j]:mp)
		j=CC++;
	mp[1e18]=CC;
	for(int i=0;i<n;i++) l[i]=L[i],
		sus.setdungeon(i,w[i],p[i]);
	sus.setdungeon(n,n,0),
	sus.preproc(n);
}

long long simulate(int x, int Z) {
	long long z=Z;
	while(1){
		if(sus.strongest(x,24)<=Z)
			return z+sus.strength(x,24);
		long long add=0;
		for(int i=24;i--;)
			if(sus.strongest(x,i)<=Z)
				add+=sus.strength(x,i),
				x=sus.dungeon(x,i);
		z+=add;
		int K=sus.strength(x,0);
		if(z>=sus.strongest(x,0))
			x=sus.dungeon(x,0);
		else x=l[x];
		z+=K;
	}
}

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