Submission #829392

#	Time	Username	Problem	Language	Result	Execution time	Memory
829392		NothingXD	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	480 ms	884324 KiB

dungeons

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 5e4 + 10;
const int lg = 30;
const ll inf = 1e18;

int n, s[maxn], p[maxn], w[maxn], l[maxn];
int par[lg][lg][maxn];
ll mn[lg][lg][maxn];
ll sum[lg][lg][maxn];


void init(int _n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _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];
	}
	w[n] = l[n] = n;
	for (int i = 0; i < lg; i++){
		for (int k = 0; k <= n; k++){
			if (s[k] > (1 << i)){
				sum[i][0][k] = p[k];
				mn[i][0][k] = s[k];
				par[i][0][k] = l[k];
			}
			else{
				sum[i][0][k] = s[k];
				mn[i][0][k] = inf;
				par[i][0][k] = w[k];
			}
		}
		for (int j = 1; j < lg; j++){
			for (int k = 0; k <= n; k++){
				ll tmp = mn[i][j-1][par[i][j-1][k]];
				mn[i][j][k] = min(mn[i][j-1][k], tmp - sum[i][j-1][k]);
				par[i][j][k] = par[i][j-1][par[i][j-1][k]];
				sum[i][j][k] = sum[i][j-1][k] + sum[i][j-1][par[i][j-1][k]];
			}
		}
	}
}

int lst = -1;

ll solve(int x, ll z){
	if (x == n) return z;
	int ptr = 31 - __builtin_clz(z);
	ptr = min(ptr, lg-1);
	if (ptr == lst) assert(0);
	lst = ptr;
	//debug(ptr);
	int v = x;
	ll cnt = z;
	for (int i = lg-1; ~i; i--){
	//	debug(i, v, mn[ptr][i][v], par[ptr][i][v], sum[ptr][i][v], cnt);
		if (par[ptr][i][v] == n || mn[ptr][i][v] <= cnt) continue;
		cnt += sum[ptr][i][v];
		v = par[ptr][i][v];
	}
	//debug(v, cnt);
	cnt += s[v];
	v = w[v];
	//debug(v, cnt);
	return solve(v, cnt);
}

long long simulate(int x, int z) {
	lst = -1;
	return solve(x, z);
}

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