Submission #1195933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195933		Ludissey	Dungeons Game (IOI21_dungeons)	C++20	11 / 100	7114 ms	564840 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

using namespace std;

int N; 
vector<int> s,p;
vector<vector<int>> nxtW,mxW,w,l,nxtL,mnL;
int avg=0;
const int LOG=24;


void init(signed n, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L) {
	N=n;
	s.resize(N+1);
	p.resize(N);
	w.resize(N+1,vector<int>(LOG,N));
	l.resize(N+1,vector<int>(LOG,N));
	nxtW.resize(N+1,vector<int>(LOG,0));
	nxtL.resize(N+1,vector<int>(LOG,0));
	mxW.resize(N+1,vector<int>(LOG,0));
	mnL.resize(N+1,vector<int>(LOG,0));
	w[N][0]=N;
	s[N]=0;
	avg=0;
	for (int i = 0; i < n; i++)
	{
		s[i]=S[i];
		p[i]=P[i];
		w[i][0]=W[i];
		l[i][0]=L[i];
		nxtW[i][0]=s[i];
		mxW[i][0]=s[i];
		mnL[i][0]=s[i];
		nxtL[i][0]=p[i];
		avg+=s[i];
	}
	avg/=N;
	for (int j = 1; j < LOG; j++)
	{
		for (int i = 0; i < N; i++)
		{
			w[N][j]=N;
			l[N][j]=N;
			w[i][j]=w[w[i][j-1]][j-1];
			l[i][j]=l[l[i][j-1]][j-1];
			nxtW[i][j]=nxtW[i][j-1]+nxtW[w[i][j-1]][j-1];
			nxtL[i][j]=nxtL[i][j-1]+nxtL[l[i][j-1]][j-1];
			mxW[i][j]=max(mxW[i][j-1],mxW[w[i][j-1]][j-1]-nxtW[i][j-1]);
			mnL[i][j]=min(mnL[i][j-1],mnL[l[i][j-1]][j-1]-nxtL[i][j-1]);
		}
	}
	return;
}

long long simulate(signed x, signed z) {
	int cs=z;
	int u=x;
	int j=0;
	while(u!=N){
		if(s[u]>cs){
			if(s[u]>cs) {
				cs+=p[u];
				u=l[u][0];
				continue;
			}
			int v=u;
			for (int j = LOG-1; j >= 0; j--)
			{
				if(mxW[v][j]>cs) continue;
				cs+=nxtW[v][j];
				v=w[v][j];
				if(v==N) return cs;
			}
			cs+=p[v];
			u=l[v][0];
		}else{
			j++;
			if(s[u]<=cs) {
				cs+=s[u];
				u=w[u][0];
				continue;
			}
			int v=u;
			for (int j = LOG-1; j >= 0; j--)
			{
				if(mnL[v][j]<=cs) continue;
				cs+=nxtL[v][j];
				v=l[v][j];
				if(v==N) return cs;
			}
			cs+=s[v];
			u=w[v][0];
		}
		assert(j<=5);
	}
	return cs;
}

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