Submission #609658

#	Time	Username	Problem	Language	Result	Execution time	Memory
609658		FEDIKUS	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	2171 ms	738440 KiB

dungeons

#include<bits/stdc++.h>
#include "dungeons.h"

using namespace std;

typedef long long ll;

const int logz=25;
const int logn=25;
const int maxn=50000+10;

struct{
	ll gain,max;
	int pos;
} lift[maxn][logz][logn];

int n;
vector<int> s,p;
vector<int> w,l;

void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
	n=nn; s=ss; p=pp; w=ww; l=ll;
	s.resize(n+1); p.resize(n+1); w.resize(n+1), l.resize(n+1);
	s[n]=0; p[n]=0; w[n]=n; l[n]=n;
	for(int bit=0;bit<logz;bit++){
		for(int jump=0;jump<logn;jump++){
			for(int pos=0;pos<=n;pos++){
				if(jump==0){
					if((1<<bit)>=s[pos]) lift[pos][bit][jump]={s[pos],LLONG_MIN,w[pos]};
					else lift[pos][bit][jump]={p[pos],-s[pos],l[pos]};
				}else{
					lift[pos][bit][jump]={lift[pos][bit][jump-1].gain+lift[lift[pos][bit][jump-1].pos][bit][jump-1].gain,
									      max(lift[pos][bit][jump-1].max,lift[pos][bit][jump-1].gain+lift[lift[pos][bit][jump-1].pos][bit][jump-1].max),
										  lift[lift[pos][bit][jump-1].pos][bit][jump-1].pos};
				}
			}
		}
	}
	return;
}

int get_bit(ll a){
	return min(63-__builtin_clzll(a),logz-1);
}

long long simulate(int x, int z) {
	long long res=z;
	while(true){
		if(res==0){
			res=p[x];
			x=l[x];
			continue;
		}
		int bit=get_bit(res);
		for(int jump=logn-1;jump>=0;jump--){
			if(res+lift[x][bit][jump].max<0){
				res+=lift[x][bit][jump].gain;
				x=lift[x][bit][jump].pos;
			}
		}
		if((1LL<<bit)<s[x] && res>=s[x]){
			res+=s[x];
			x=w[x];
		}
		if(x==n) break;
	}
	return res;
}

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