Submission #465173

#	Time	Username	Problem	Language	Result	Execution time	Memory
465173		flappybird	Dungeons Game (IOI21_dungeons)	C++17	89 / 100	7158 ms	1730688 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

#define MAXS 27 //MAX sparse table
#define MAXI 8 //MAX interval
#define B 3
#define INF 101010101010101010
#define MAX 400400

vector<pll> win, lose; //next
int nxt[MAX][MAXI][MAXS];
ll delta[MAX][MAXI][MAXS], limit[MAX][MAXI][MAXS];
int N;

ll dp[MAX];

ll get(ll x) {
	if (x == N) return 0;
	if (dp[x]) return dp[x];
	return dp[x] = get(win[x].first) + win[x].second;
}

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	N = n;
	ll i;
	win.resize(N + 1);
	lose.resize(N + 1);
	for (i = 0; i < N; i++) {
		win[i] = { w[i], s[i] };
		lose[i] = { l[i], p[i] };
	}
	ll k;
	for (k = 0; k < MAXI; k++) {
		ll low, high;
		low = 1 << B * k;
		high = 1 << (B * (k + 1));
		for (i = 0; i < N; i++) {
			if (s[i] < low) {
				nxt[i][k][0] = win[i].first;
				delta[i][k][0] = win[i].second;
				limit[i][k][0] = INF;
			}
			else if (s[i] >= high) {
				nxt[i][k][0] = lose[i].first;
				delta[i][k][0] = lose[i].second;
				limit[i][k][0] = s[i];
			}
			else {
				nxt[i][k][0] = lose[i].first;
				delta[i][k][0] = lose[i].second;
				limit[i][k][0] = s[i];
			}
		}
		nxt[N][k][0] = N;
		delta[N][k][0] = 0;
		limit[N][k][0] = INF;
		ll j;
		for (j = 1; j < MAXS; j++) {
			for (i = 0; i <= N; i++) {
				ll v = nxt[i][k][j - 1];
				nxt[i][k][j] = nxt[v][k][j - 1];
				delta[i][k][j] = delta[i][k][j - 1] + delta[v][k][j - 1];
				limit[i][k][j] = max(0LL, min(limit[v][k][j - 1] - delta[i][k][j - 1], limit[i][k][j - 1]));
			}
		}
	}
	for (i = 0; i <= N; i++) get(i);
	return;
}

void move(int& x, ll& z) {
	if (z >= win[x].second) z += win[x].second, x = win[x].first;
	else z += lose[x].second, x = lose[x].first;
}

long long simulate(int x, int Z) {
	ll z = Z;
	ll i;
	for (i = 0; i < MAXI; i++) {
		if (x == N) break;
		if (z >= 10000000) break;
		ll high;
		high = 1 << (B * (i + 1));
		if (high <= z) continue;
		if (x == N) return z;
		if (z >= 10000000) return z + dp[x];
		ll k;
		while (z < high) {
			for (k = MAXS - 1; k >= 0; k--) {
				if (nxt[x][i][k] != N && limit[x][i][k] > z && delta[x][i][k] < 10000000) z += delta[x][i][k], x = nxt[x][i][k];
				if (z >= high) break;
			}
			if (x == N) return z;
			if (z >= high) break;
			if (x != N && z < high) move(x, z);
		}
	}
	return z + dp[x];
}

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