Submission #829460

#	Time	Username	Problem	Language	Result	Execution time	Memory
829460		NothingXD	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2713 ms	1904260 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 = 4e5 + 10;
const int lg = 20;
const int st = 5;
const int inf = 1e9;

int n, s[maxn], p[maxn], w[maxn], l[maxn];
int par[lg][lg][maxn];
int mn[lg][lg][maxn];
int sum[lg][lg][maxn];
ll val[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+st))){
				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 <= st; j++){
			for (int k = 0; k <= n; k++){
				int 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]);
				mn[i][j][k] = max(mn[i][j][k], 0);
				par[i][j][k] = par[i][j-1][par[i][j-1][k]];
				sum[i][j][k] = min((int)1e7, sum[i][j-1][k] + sum[i][j-1][par[i][j-1][k]]);
			}
		}

		for (int k = 0; k <= n; k++){
				sum[i][0][k] = sum[i][st][k];
				mn[i][0][k] = mn[i][st][k];
				par[i][0][k] = par[i][st][k];
		}

		for (int j = 1; j < lg; j++){
			for (int k = 0; k <= n; k++){
				int 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]);
				mn[i][j][k] = max(mn[i][j][k], 0);
				par[i][j][k] = par[i][j-1][par[i][j-1][k]];
				sum[i][j][k] = min((int)1e7, sum[i][j-1][k] + sum[i][j-1][par[i][j-1][k]]);
			}
		}
	}
	for (int i = n-1; ~i; i--){
		val[i] = val[w[i]] + s[i];
	}
	debug(1);
}

int lst = -1;

ll solve(int x, ll z){
//	debug(x, z);
	if (x == n) return z;
	if (z >= 1e7) return z + val[x];
	int ptr = 31 - __builtin_clz(z);
	ptr -= st;
	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 (sum[ptr][i][v] + cnt >= 1e7 || par[ptr][i][v] == n || mn[ptr][i][v] <= cnt) continue;
		cnt += sum[ptr][i][v];
		v = par[ptr][i][v];
	}
	//debug(v, cnt);
	int tmp = (1 << st);
//	debug(0, v, cnt);
	while(tmp--){
		if (cnt >= s[v]){
			cnt += s[v];
			v = w[v];
		}
		else{
			cnt += p[v];
			v = l[v];
		}
	}
	//debug(1, v, cnt);
	return solve(v, cnt);
}

long long simulate(int x, int z) {
	lst = -1;
	ll cnt = z;
	while(x != n && cnt < (1 << st)){
		if (cnt >= s[x]){
			cnt += s[x];
			x = w[x];
		}
		else{
			cnt += p[x];
			x = l[x];
		}
	}
	return solve(x, cnt);
}

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