Submission #437518

#	Time	Username	Problem	Language	Result	Execution time	Memory
437518		QAQAutoMaton	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2768 ms	775472 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace ns{
	int n,m;	
	int s[400005],p[400005],w[400005],l[400005];
	int toe[400005];
	//int f[21][400005],g[21][400005],h[21][400005];
	struct arr{
		signed v[400005];
		signed &operator [](int b){return v[b];}
	};
	arr tb[505],*f[12],*g[12],*h[12],*las=tb;
	arr *neww(int n){
		arr *ret=las;las+=n;return ret;
	}
	int a[400005];
	const signed inf=0x3f3f3f3f;
	int pw[25];
	void init(signed N, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L) {
		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];
		/*for(int i=0;i<n;++i)a[i+1]=s[i];
		sort(a+1,a+n+1);
		m=unique(a+1,a+n+1)-a-1;
		for(int v=0;v<=m;++v){
			for(int i=0;i<n;++i){
				f[v][0][i]=(s[i]<=a[v]?w[i]:l[i]);
				g[v][0][i]=(s[i]<=a[v]?s[i]:p[i]);
			}
			f[v][0][n]=n;g[v][0][n]=0;
			for(int i=1;i<=30;++i)for(int j=0;j<=n;++j){
				f[v][i][j]=f[v][i-1][f[v][i-1][j]];
				g[v][i][j]=g[v][i-1][j]+g[v][i-1][f[v][i-1][j]];
			}
		}*/
		for(int i=n-1;~i;--i)toe[i]=s[i]+toe[w[i]];
		for(int i=0;i<=12;++i)pw[i]=1<<(i+i);
		for(int v=0;v<12;++v){
			f[v]=neww(v+v+2);
			g[v]=neww(v+v+2);
			h[v]=neww(v+v+2);
			for(int i=0;i<n;++i){
				if(s[i]<pw[v]){
					f[v][0][i]=w[i];
					g[v][0][i]=s[i];
					h[v][0][i]=inf;
				}
				else{
					f[v][0][i]=l[i];
					g[v][0][i]=p[i];
					h[v][0][i]=s[i];
				}
			}
			f[v][0][n]=n;g[v][0][n]=0;h[v][0][n]=inf;
			for(int i=1;i<=v+v+1;++i){
				for(int j=0;j<=n;++j){
					f[v][i][j]=f[v][i-1][f[v][i-1][j]];
					g[v][i][j]=min(g[v][i-1][j]+g[v][i-1][f[v][i-1][j]],inf);
					h[v][i][j]=max(min(h[v][i-1][j],h[v][i-1][f[v][i-1][j]]-g[v][i-1][j]),-1);
				}
			}

		}
		/*for(int i=0;i<n;++i){
			f[0][i]=w[i],g[0][i]=s[i],h[0][i]=s[i];
		}
		f[0][n]=n;g[0][n]=h[0][n]=0;
		for(int i=1;i<=20;++i){
			for(int j=0;j<=n;++j){
				f[i][j]=f[i-1][f[i-1][j]];
				g[i][j]=max(g[i-1][j],g[i-1][f[i-1][j]]-h[i-1][j]);
				h[i][j]=h[i-1][j]+h[i-1][f[i-1][j]];
			}
		}*/
	}
	long long simulate(int x, int z) {
		int rk=0;
		while(x<n){
			if(z>=pw[rk+1]&&rk<12)++rk;
			if(rk==12){
				return z+toe[x];
			}
			for(int i=rk+rk+1;~i;--i){
				if(z<h[rk][i][x] && g[rk][i][x]+z<pw[rk+1]){
					z+=g[rk][i][x];
					x=f[rk][i][x];
				}
			}
			if(x<n){
				if(z>=s[x]){
					z+=s[x];x=w[x];
				}
				else{
					z+=p[x];x=l[x];
				}
			}
		}
		return z;
		/*while(x<n){
			for(int i=20;~i;--i){
				if(z>=g[i][x]){
					z+=h[i][x];
					x=f[i][x];
				}
			}
			if(x<n){
				z+=p[x];x=l[x];
			}
		}*/

		/*	if(z>=s[x]){
				z+=s[x];x=w[x];
			}
			else{
				z+=p[x];x=l[x];
			}
		}*/
		return z ;
	}
}
void init(signed N, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L) {
	ns::init(N,S,P,W,L);
}

long long simulate(signed x, signed z) {
	return ns::simulate(x,z);
}

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