Submission #1035010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035010		hotboy2703	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7053 ms	206928 KiB

dungeons

#include "dungeons.h"

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
const ll MAXN = 4e5+100;
const ll MAXK = 19;
struct path{
	ll x,max1,sum;
};
path sp[MAXK][MAXN];
vector <int> s,p,w,l;
ll n;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
	n=N;
	s=S,p=P,w=W,l=L;
	for (ll i = 0;i < n;i ++)sp[0][i] = {w[i],s[i],s[i]};
	sp[0][n] = {n,0,0};
	for (ll j = 1;j < MAXK;j ++){
		for (ll i = 0;i <= n;i ++){
			sp[j][i].x = sp[j-1][sp[j-1][i].x].x;
			sp[j][i].max1 = max(sp[j-1][i].max1,sp[j-1][sp[j-1][i].x].max1);
			sp[j][i].sum = sp[j-1][i].sum + sp[j-1][sp[j-1][i].x].sum;
		}
	}
	return;
}

long long simulate(int x, int Z) {
	ll z=Z;
	while (x!=n){
		for (ll j = MAXK-1;j>=0;j--){
			if (sp[j][x].max1 <= z){
				z += sp[j][x].sum;
				x = sp[j][x].x;
			}
		}
		if (x!=n && z < s[x]){
			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