Submission #600376

#	Time	Username	Problem	Language	Result	Execution time	Memory
600376		idiot123	Dungeons Game (IOI21_dungeons)	C++17	89 / 100	7165 ms	1641984 KiB

dungeons

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

using namespace std;

//we will use powers of 4 to decide what is the best jump
const int MAX_BIT = 13;
//jumps are base 3 to save memory
const int MAX_JUMP = 16;
const long long INF = 1e18;
vector<array<array<int, MAX_JUMP>, MAX_BIT>> jump;
vector<array<array<long long, MAX_JUMP>, MAX_BIT>> maxVal;
vector<array<array<long long, MAX_JUMP>, MAX_BIT>> sum;
int N;

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
	N = n;
	vector<bool> vis(n+1, false);
	jump.resize(n+1);
	maxVal.resize(n+1);
	sum.resize(n+1);
	for(int i = 0; i < n; i++){
		for(int bit = 0; bit < MAX_BIT; bit++){
			if((1<<(2*bit)) >= s[i]){
				jump[i][bit][0] = w[i];
				maxVal[i][bit][0] = INF;
				sum[i][bit][0] = s[i];
			}else{
				jump[i][bit][0] = l[i];
				maxVal[i][bit][0] = s[i]-1;
				sum[i][bit][0] = p[i];
			}
		}
	}
	for(int bit = 0; bit < MAX_BIT; bit++){
		jump[n][bit][0] = n;
		maxVal[n][bit][0] = INF;
		sum[n][bit][0] = 0;
	}
	for(int l = 1; l < MAX_JUMP; l++){
		for(int i = 0; i <= n; i++){
			for(int bit = 0; bit < MAX_BIT; bit++){
				int a, b, c;
				a = jump[i][bit][l-1];
				b = jump[a][bit][l-1];
				c = jump[b][bit][l-1];
				//d = jump[c][bit][l-1];
				jump[i][bit][l] = c;
				sum[i][bit][l] = sum[i][bit][l-1] + sum[a][bit][l-1] + sum[b][bit][l-1];// + sum[c][bit][l-1];
				maxVal[i][bit][l] = min(min(maxVal[i][bit][l-1], maxVal[a][bit][l-1] - sum[i][bit][l-1]),maxVal[b][bit][l-1] - sum[a][bit][l-1]  - sum[i][bit][l-1]); 
			}
		}
	}
}

long long simulate(int x, int z){
	long long val = z;
	int bit = 0;
	int xd = 1;
	while(bit < MAX_BIT-1 && 4 * xd <= val){
		bit++; xd *= 4;
	}
	while(x != N){
		for(int i = MAX_JUMP-1; i >= 0; i--){
			while(x != N && val <= maxVal[x][bit][i]){
				val += sum[x][bit][i];
				x = jump[x][bit][i];
			}
		}
		if(x != N){
			val += sum[x][MAX_BIT -1][0];
			x = jump[x][MAX_BIT-1][0];
		}
		while(bit < MAX_BIT-1 && 4 * xd <= val){
			bit++; xd *= 4;
		}
	}
	return val;
}

/*
int main(){
	int n, q; cin>>n>>q;
	vector<int> s(n), p(n), w(n), l(n);
	for(int i = 0; i < n; i++)cin>>s[i];
	for(int i = 0; i < n; i++)cin>>p[i];
	for(int i = 0; i < n; i++)cin>>w[i];
	for(int i = 0; i < n; i++)cin>>l[i];
	init(n, s, p, w, l);
	for(int j = 0; j < q; j++){
		int x, z; cin>>x>>z;
		cout<<simulate(x, z)<<"\n";
	}
}
*/

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