Submission #817937

#	Time	Username	Problem	Language	Result	Execution time	Memory
817937		Username4132	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7079 ms	151356 KiB

dungeons

#include "dungeons.h"
#include<iostream>
#include <vector>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)

const int MAXN = 400010, LG = 21;
int s[MAXN], w[MAXN], l[MAXN], p[MAXN];
int n, up[LG][MAXN], mx[LG][MAXN];
ll cst[LG][MAXN];

void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
	n = _n;
	forn(i, n) s[i]=_s[i], p[i]=_p[i], w[i]=_w[i], l[i]=_l[i];
	w[n]=l[n]=n;
	s[n]=p[n]=0;
	forn(i, n+1){
		up[0][i]=w[i];
		cst[0][i]=s[i];
		mx[0][i]=s[i];
	}
	forn(i, LG-1) forn(j, n+1){
		up[i+1][j] = up[i][up[i][j]];
		mx[i+1][j] = max(mx[i][j], mx[i][up[i][j]]);
		cst[i+1][j] = cst[i][j] + cst[i][up[i][j]];
	}

	return;
}

long long simulate(int _x, int _z) {

	int x = _x;
	ll z = _z;
	while(x!=n){
		dforn(i, LG) if(mx[i][x] <= z){
			z += cst[i][x];
			bool flag = x != up[i][x];
			x = up[i][x];
			if(flag) i = LG - 1;
		}
		if(s[x] <= z){
			z += s[x];
			x = w[x];
		}
		else{
			z += p[x];
			x = l[x];
		}
	}
	return z;
}

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