Submission #599389

#	Time	Username	Problem	Language	Result	Execution time	Memory
599389		Lucpp	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	7108 ms	2058420 KiB

dungeons

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

struct Data{
	int pos;
	ll sum, need;
};
Data combine(Data a, Data b){
	Data c;
	c.pos = b.pos;
	c.sum = a.sum + b.sum;
	c.need = min(a.need, b.need-a.sum);
	return c;
}

int n;
vector<int> s, p, w, l;
vector<vector<vector<Data>>> jump;

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_;
	jump.assign(LOG/SIZE, vector<vector<Data>>(LOG, vector<Data>(n+1)));
	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], s[j], INF};
			else jump[i][0][j] = {l[j], p[j], s[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 = 0; layer <= LOG/SIZE && ans >= (1<<(layer*SIZE)); layer++);
		layer--;
		Data d{x, ans, INF};
		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