Submission #817939

#	Time	Username	Problem	Language	Result	Execution time	Memory
817939		FEDIKUS	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	7076 ms	845012 KiB

dungeons

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

using namespace std;

typedef long long ll;

const int logz=13;
const int logn=26;
const int maxn=50000+10;

struct{
	ll gain,max;
	int pos;
} lift[logz][logn][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],LLONG_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};
				}
			}
		}
	}
	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;
	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[bit][jump][x].max<0){
				res+=lift[bit][jump][x].gain;
				x=lift[bit][jump][x].pos;
			}
		}
		assert(x==n || ((1LL<<2*bit)<s[x] && res>=s[x]));
		if((1LL<<2*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: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11