Submission #599436

#	Time	Username	Problem	Language	Result	Execution time	Memory
599436		Lucpp	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	7056 ms	921528 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int SIZE = 4;
const int LOG = 24;

struct Data{
	int pos, need;
	ll sum;
};
Data combine(Data a, Data b){
	Data c;
	c.pos = b.pos;
	c.sum = a.sum + b.sum;
	if(b.need == -1) c.need = a.need;
	else if(b.need <= a.sum) c.need = 0;
	else if(a.need != -1) c.need = min(a.need, b.need-(int)a.sum);
	else c.need = b.need-(int)a.sum;
	return c;
}

int n;
vector<int> s, p, w, l;
Data jump[LOG/SIZE][LOG][int(4e5+1)];

void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_) {
	n = n_, s = s_, p = p_, w = w_, l = l_;
	for(int i = 0; i < LOG/SIZE; i++){
		for(int j = 0; j < n; j++){
			if(s[j] <= (1<<(i*SIZE))) jump[i][0][j] = {w[j], -1, s[j]};
			else jump[i][0][j] = {l[j], s[j], p[j]};
		}
		jump[i][0][n] = {n, 0, 0};
		for(int k = 1; k < LOG; k++){
			for(int j = 0; j <= n; j++){
				jump[i][k][j] = combine(jump[i][k-1][j], jump[i][k-1][jump[i][k-1][j].pos]);
			}
		}
	}
}

ll simulate(int x, int z) {
	ll ans = z;
	while(x != n){
		if(ans >= s[x]){
			ans += s[x];
			x = w[x];
			continue;
		}
		int layer;
		for(layer = 1; layer <= LOG/SIZE && ans >= (1<<(layer*SIZE)); layer++);
		layer--;
		Data d{x, -1, ans};
		for(int k = LOG-1; k >= 0; k--){
			Data d2 = combine(d, jump[layer][k][d.pos]);
			if(d2.need > 0) d = d2;
		}
		ans = d.sum;
		x = d.pos;
	}
	return ans;
}

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