Submission #829414

#	Time	Username	Problem	Language	Result	Execution time	Memory
829414		fatemetmhr	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	5614 ms	214504 KiB

dungeons

// Be Name Khoda //


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

using namespace std;

#define MAX(x, y)  ((x) > (y) ? (x) : (y))
#define MIN(x, y)  ((x) < (y) ? (x) : (y))
#define debug(x)   cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)     (x).begin(), (x).end()
#define fi         first
#define se         second
#define pb         push_back
#define mp         make_pair

typedef long long ll;

const int maxn5 = 5e4 + 10;
const int ssq   = 3200;
const int lg    = 25;

int n, par[7][lg][maxn5], pt[maxn5];
int s[maxn5], p[maxn5], w[maxn5], l[maxn5];
ll val[7][lg][maxn5];
vector <int> have;

void init(int nn, std::vector<int> ss, std::vector<int> pp, std::vector<int> ww, std::vector<int> ll) {
	n = nn;
	for(int i = 0; i < n; i++){
		s[i] = ss[i];
		p[i] = pp[i];
		w[i] = ww[i];
		l[i] = ll[i];
		have.pb(s[i]);
	}
	sort(all(have));
	have.resize(unique(all(have)) - have.begin());
	have.pb(1e7 + 2);
	for(int i = 0; i < n; i++)
		pt[i] = lower_bound(all(have), s[i]) - have.begin();
	memset(par, -1, sizeof par);
	for(int i = 0; i < int(have.size()); i++){
		for(int j = 0; j < n; j++){
			par[i][0][j] = (pt[j] < i ? w[j] : l[j]);
			val[i][0][j] = (pt[j] < i ? s[j] : p[j]);
		}
		for(int x = 1; x < lg; x++) for(int j = 0; j < n; j++)
			if(par[i][x - 1][j] != -1){
				par[i][x][j] = par[i][x - 1][par[i][x - 1][j]];
				val[i][x][j] = val[i][x - 1][j] + val[i][x - 1][par[i][x - 1][j]];
			}
	}

	return;
}

long long simulate(int x, int zz) {
	ll ret = zz;
	while(x < n){
		int lev = upper_bound(all(have), ret) - have.begin();
		//debug(lev);
		//debug(have[lev]);
		if(lev == int(have.size()) - 1){
			for(int i = lg - 1; i >= 0; i--) if(par[lev][i][x] != -1){
				ret += val[lev][i][x];
				x = par[lev][i][x];
			}
			return ret;
		}

		for(int i = lg - 1; i >= 0; i--)
			if(par[lev][i][x] != -1 && ret + val[lev][i][x] < have[lev]){
				ret += val[lev][i][x];
				x = par[lev][i][x];
			}
		//debug(x);
		//debug(ret);
		if(x < n){
			if(ret < s[x]){
				ret += p[x];
				x = l[x];
			}
			else{
				ret += s[x];
				x = w[x];
			}
		}
		//debug(x);
		//debug(ret);
	}
	return ret;
}

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