Submission #830077

#	Time	Username	Problem	Language	Result	Execution time	Memory
830077		fatemetmhr	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3957 ms	1914284 KiB

dungeons

// Be Name Khoda //
 
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops,O3")
 
#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 = 4e5 + 5;//4e2 + 5;
const int lgr   = 25;
const int lgl   = 13;
 
int n, par[lgr - lgl + 1][lgr][maxn5];
int s[maxn5], p[maxn5], w[maxn5], l[maxn5];
ll val[lgr - lgl][lgr][maxn5];
int mn[lgr - lgl][lgr][maxn5];
 
 
int get_lev(ll x){
	return 63 - __builtin_clzll(x);
}
 
 
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];
	}
 
	memset(par, -1, sizeof par);
 
	for(int x = 0; x < lgr - lgl; x++){
		for(int i = 0; i < n; i++){
			int re = ((1 << (x + lgl)) >= s[i]);
			par[x][0][i] = re ? w[i] : l[i];
			val[x][0][i] = re ? s[i] : p[i];
			mn[x][0][i] = re ? -1 : s[i];
		}
		for(int k = 1; k < lgr; k++)
			for(int i = 0; i < n; i++) if(par[x][k - 1][i] != -1){
				int v = par[x][k - 1][i];
				par[x][k][i] = par[x][k - 1][v];
				val[x][k][i] = val[x][k - 1][i] + val[x][k - 1][v];
				mn[x][k][i] = mn[x][k - 1][i];
				if(mn[x][k - 1][v] != -1 && (mn[x][k - 1][i] == -1 || mn[x][k - 1][v] - val[x][k - 1][i] < mn[x][k][i]))
					mn[x][k][i] = max(0ll, mn[x][k - 1][v] - val[x][k - 1][i]);
			}
	}
	return;
}
 
long long simulate(int x, int zz) {
	ll ret = zz;
	while(ret < (1 << lgl) && x < n){
		bool re = ret >= s[x];
		ret += (re ? s[x] : p[x]);
		x = (re ? w[x] : l[x]);
	}
	int last = -1;
	while(x < n){
		int lev = get_lev(ret);
		lev = min(lev, lgr - 1);
		if(lev < lgr - 1 && lev == last && false)
			exit(0);
		last = lev;
		//debug("*******");
		//debug(lev);
		//debug(x);
		//debug(ret);
		lev -= lgl;
		for(int i = lgr - 1; i >= 0; i--){
			//debug(i);
			//debug(x);
			//debug(ret);
			//debug(mn[lev][i][x]);
			//debug(par[lev][i][x]);
			if(par[lev][i][x] != -1 && (mn[lev][i][x] == -1 || mn[lev][i][x] > ret)){
				ret += val[lev][i][x];
				x = par[lev][i][x];
			}
		}
		if(x == n)
			return ret;
		//debug("here");
		//debug(x);
		//debug(ret);
		//debug(s[x]);
		//debug(mn[lev][0][x]);
		//debug(w[x]);
		//debug(l[x]);
		if(s[x] <= (1 << (lev + lgl)))
			return -1;
		bool re = ret >= s[x];
		if(!re && false)
			exit(0);
		ret += (re ? s[x] : p[x]);
		x = (re ? w[x] : l[x]);
	}
	return ret;
}
 
 
 

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