Submission #832572

#	Time	Username	Problem	Language	Result	Execution time	Memory
832572		DJeniUp	Dungeons Game (IOI21_dungeons)	C++17	50 / 100	7050 ms	971732 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll>pairll;

#define N 100007
#define fr first
#define sc second
#define A 38

ll n,s[4*N],p[4*N],w[4*N],l[4*N],k[4*N],mx[4*N];

struct D{
	ll mxs,mns,dp,ds,pw,pl;
}d[4*N][50];

void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
	n=_n+1;
	for(int i=1;i<n;i++){
		s[i]=_s[i-1];
		p[i]=_p[i-1];
		w[i]=_w[i-1]+1;
		l[i]=_l[i-1]+1;
		d[i][0]={s[i]+s[i],s[i]+p[i],p[i],s[i],w[i],l[i]};
	}
	for(int i=1;i<=A;i++){
		for(int j=1;j<=n-1;j++){
			d[j][i].mxs=max(d[d[j][i-1].pw][i-1].mxs,d[j][i-1].mxs+d[d[j][i-1].pw][i-1].ds);
			d[j][i].mns=min(d[d[j][i-1].pl][i-1].mns,d[j][i-1].mns+d[d[j][i-1].pl][i-1].dp);
			d[j][i].dp=d[j][i-1].dp+d[d[j][i-1].pl][i-1].dp;
			d[j][i].ds=d[j][i-1].ds+d[d[j][i-1].pw][i-1].ds;
			d[j][i].pw=d[d[j][i-1].pw][i-1].pw;
			d[j][i].pl=d[d[j][i-1].pl][i-1].pl;
		}
	}
	for(int i=n-1;i>=1;i--){
		k[i]=k[w[i]]+s[i];
		mx[i]=max(mx[w[i]],s[i]);
	}
	return ;
}

pairll S0(ll x,ll y){
	for(int i=A;i>=0;i--){
		if(d[x][i].mns>y+d[x][i].dp){
			y+=d[x][i].dp;
			x=d[x][i].pl;
		}
	}
	return make_pair(x,y);
}

pairll S1(ll x,ll y){
	for(int i=A;i>=0;i--){
		if(d[x][i].mxs<=y+d[x][i].ds){
			y+=d[x][i].ds;
			x=d[x][i].pw;
		}
	}
	return make_pair(x,y);
}

long long simulate(int _x, int _z) {
	ll x=_x;
	ll z=_z;
	x++;
	ll tp=0;
	if(s[x]<=z)tp=1;
	while(x!=0 && x<n){
		if(tp==0){
			pairll m1=S0(x,z);
			x=m1.fr;
			z=m1.sc;
		}else{
			pairll m1=S1(x,z);
			x=m1.fr;
			z=m1.sc;
		}
		tp^=1;
	}
    return z;
}

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