Submission #817948

#	Time	Username	Problem	Language	Result	Execution time	Memory
817948		FEDIKUS	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	4279 ms	1443804 KiB

dungeons

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

using namespace std;

typedef long long ll;

const int logz=12;
const int logn=25;
const int maxn=8*50000+10;
const int inf=1e7+10;

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

ll dokraja[maxn];
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*2)>=s[pos]) lift[bit][jump][pos]={s[pos],INT_MIN,w[pos]};
					else lift[bit][jump][pos]={p[pos],-s[pos],l[pos]};
				}else{
					lift[bit][jump][pos]={lift[bit][jump-1][pos].gain+lift[bit][jump-1][lift[bit][jump-1][pos].pos].gain,
									      max(lift[bit][jump-1][pos].max,lift[bit][jump-1][pos].gain+lift[bit][jump-1][lift[bit][jump-1][pos].pos].max),
										  lift[bit][jump-1][lift[bit][jump-1][pos].pos].pos};
					if(lift[bit][jump][pos].gain>inf){
						lift[bit][jump][pos].gain=inf;
						lift[bit][jump][pos].max=1;
					}
				}
			}
		}
	}
	for(int i=n;i>=0;i--){
		dokraja[i]=dokraja[w[i]]+s[i];
	}
	return;
}

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

long long simulate(int x, int z) {
	long long res=z;
	int klk=0;
	while(true){
		klk++;
		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[bit][jump][x].max<0){
				res+=lift[bit][jump][x].gain;
				x=lift[bit][jump][x].pos;
			}
		}
		if((1LL<<2*bit)<s[x] && res>=s[x]){
			res+=s[x];
			x=w[x];
		}
		if(res>inf){
			res+=dokraja[x];
			break;	
		}
		if(x==n) break;
	}
	return res;
}

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