Submission #1036186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036186		Mardonbekhazratov	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	65 ms	29684 KiB

dungeons

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

using namespace std;

#define ll long long

int n;
vector<ll>dp;
vector<int>s,p,w,l;
vector<vector<ll>>sum,up;
const int lg=30;

void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
	swap(n,N);
	swap(S,s);
	swap(P,p);
	swap(W,w);
	swap(L,l);
	dp.resize(n+1);
	dp[n]=0;
	for(int i=n-1;i>=0;i--){
		dp[i]=dp[w[i]]+s[i];
	}
	l.push_back(n);
	p.push_back(0);
	up.assign(lg,vector<ll>(n));
	sum.assign(lg,vector<ll>(n,0));
	for(int j=0;j<lg;j++){
		for(int i=0;i<=n;i++){
			if(j==0) up[j][i]=l[i],sum[j][i]=p[i];
			else{
				up[j][i]=up[j-1][up[j-1][i]];
				sum[j][i]=sum[j-1][i]+sum[j-1][up[j-1][i]];
			}
		}
	}
}

long long simulate(int x, int z) {
	ll ans=z;
	for(int i=lg-1;i>=0;i--){
		if(ans+sum[i][x]<s[0]){
			ans+=sum[i][x];
			x=up[i][x];
		}
	}
	if(ans<s[0]){
		ans+=sum[0][x];
		x=up[0][x];
	}
	ans+=dp[x];
	return ans;
}

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