Submission #1049581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049581		vjudge1	Dungeons Game (IOI21_dungeons)	C++17	26 / 100	244 ms	177232 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
struct level {
	private:
	int bj[400100][25],mx[400100][25];
	long long inc[400100][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;
int l[400100];
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> L) {
	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: 26 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11