Submission #1197190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197190		Ludissey	Dungeons Game (IOI21_dungeons)	C++20	100 / 100	5843 ms	1931160 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#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,w,l;
vector<int> ss;
vector<vector<vector<pair<int,pair<int,int>>>>> nxt;
/*vector<vector<vector<int>>> nxt;
vector<vector<vector<int>>> nxp;*/
vector<long long> tw;

const int LOG=22;
const int MAXS=1e7;
int sn;

long long pth(int x){
	if(x==N) return 0;
	if(tw[x]>=0) return tw[x];
	tw[x]=pth(w[x])+(long long)s[x];
	return tw[x];
}

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);
	tw.resize(N,-1);
	p.resize(N);
	w.resize(N+1);
	l.resize(N+1);
	l[N]=N;
	w[N]=N;
	for (int i = 0; i < n; i++)
	{
		s[i]=S[i];
		p[i]=P[i];
		w[i]=W[i];
		l[i]=L[i];
	}
	ss.push_back(0);
	int u=1; 
	ss.push_back(u);
	while(u<MAXS){
		u*=6;
		ss.push_back(u);
	}
    sn=sz(ss);
	nxt.resize(N+1,vector<vector<pair<int,pair<int,int>>>>(sn,vector<pair<int,pair<int,int>>>(1,{0,{0,0}})));

	for (int j = 0; j < sz(ss); j++){
		nxt[N][j][0].first=0;
		nxt[N][j][0].second.first=N;
		nxt[N][j][0].second.second=1e8;
	}

	for (int i = 0; i < n; i++){
		for (int j = 0; j < sz(ss); j++)
		{
			if(s[i]<=ss[j]){
				nxt[i][j][0].first=s[i];
				nxt[i][j][0].second.first=w[i];
				nxt[i][j][0].second.second=1e8;
			}else{
				nxt[i][j][0].first=p[i];
				nxt[i][j][0].second.first=l[i];
				nxt[i][j][0].second.second=s[i];
			}
		}
	}
	for (int j = 1; j < LOG; j++)
	{
		for (int i = 0; i <= N; i++)
		{
			for (int k = 0; k < sz(ss); k++){
				if(j>sz(nxt[i][k])||nxt[i][k][j-1].second.first==N||j>sz(nxt[nxt[i][k][j-1].second.first][k])||nxt[i][k][j-1].second.second<=ss[k]||nxt[nxt[i][k][j-1].second.first][k][j-1].second.second-nxt[i][k][j-1].first<=ss[k]) continue;
				nxt[i][k].push_back({nxt[i][k][j-1].first+nxt[nxt[i][k][j-1].second.first][k][j-1].first,{nxt[nxt[i][k][j-1].second.first][k][j-1].second.first,min(nxt[i][k][j-1].second.second,nxt[nxt[i][k][j-1].second.first][k][j-1].second.second-nxt[i][k][j-1].first)}});
			}
		}
	}
	return;
}

int cs,u;

long long simulate(signed x, signed z) {
	cs=z;
	u=x;
	for (int i = 0; i < sz(ss); i++)
	{
		while(ss[i+1]>cs){
			for (int j = LOG-1; j >= 0; j--)
			{
				if(j>=sz(nxt[u][i])||nxt[u][i][j].second.first==N||nxt[u][i][j].second.second<=cs) continue;
				cs+=nxt[u][i][j].first;
				u=nxt[u][i][j].second.first;
			}
			if(nxt[u][i][0].second.first==N){
				if(s[u]>cs) cs+=p[u];
				else cs+=s[u];
				return cs;
			}else{
				if(s[u]>cs) {
					cs+=p[u];
					u=l[u];
				}
				else {
					cs+=s[u];
					u=w[u];
				}
			}
			if(u==N) return cs;
		}
	}
	return (long long)cs+pth(u);
}

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