Submission #1126887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126887		fgdsa	Dungeons Game (IOI21_dungeons)	C++20	11 / 100	7099 ms	228996 KiB

dungeons

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

using namespace std;

#define ll long long
#define para pair<ll, ll>

const ll LOG = 16;
const ll LOG2 = 24;
const ll MAXN = 50007;
const ll INF = 1e9+7;

struct Str{
	int v;
	int sum;
	int mn;
};

Str jump[MAXN][LOG][LOG2];

int n;
vector<int> s;
vector<int> p;
vector<int> w;
vector<int> l;


void gen(int x){
	int h = (1<<x);
	for(int i = 0; i < n; ++i){
		if(h < s[i]){
			jump[i][0][x] = {l[i], p[i], s[i]};
		}
		else{
			// if(i == n-1){
			// 	jump[i][0][x] = {w[i], s[i], INF};
			// }
			jump[i][0][x] = {w[i], s[i], INF};
		}
	}
	jump[n][0][x] = {n, 0, INF};

	for(int i = 1; i < LOG; ++i){
		for(int j = 0; j < n; ++j){
			Str & cur = jump[j][i][x];
			cur.v = jump[jump[j][i-1][x].v][i-1][x].v;
			cur.sum = jump[j][i-1][x].sum + jump[jump[j][i-1][x].v][i-1][x].sum;
			cur.mn = min(jump[j][i-1][x].mn, jump[jump[j][i-1][x].v][i-1][x].mn - jump[j][i-1][x].sum);


			// if(x == 1 && i == 1 && j == 0){
			// 	cerr << jump[j][i-1][x].v << " " << jump[j][i-1][x].sum << " " << jump[j][i-1][x].mn << "\n";
			// 	cerr << jump[jump[j][i-1][x].v][i-1][x].mn << "\n";
			// 	cerr << cur.v << " " << cur.sum << " " << cur.mn << "\n";
			// }
		}
	}
	return;
}

void init(int nT, vector<int> sT, vector<int> pT, vector<int> wT, vector<int> lT){
	n = nT;
	s = sT;
	p = pT;
	w = wT;
	l = lT;

	for(int i = 0; i < LOG2; ++i){
		gen(i);
	}
	
	return;
}

long long simulate(int x, int zT) {
	ll z = zT;
	ll cnt = 0;
	while(x != n){
		ll pot2 = 1;
		ll wyk = 0;
		while(pot2 * 2 <= z) pot2*=2, ++wyk;

		for(int j = LOG-1; j >= 0; --j){
			// cerr << j << ":\n";
			// cerr << "	" << x << " " << z << " " << pot2 << ": " << jump[x][j][wyk].v << " " << jump[x][j][wyk].mn << " " << jump[x][j][wyk].sum << '\n';
			if(jump[x][j][wyk].mn > z){
				z += jump[x][j][wyk].sum;
				x = jump[x][j][wyk].v;
			}
		}	
		if(x == n) break;

		z += s[x];
		x = w[x];
		// if(++cnt == 5){ 
		// 	cerr << "\n";
		// 	return 0;
		// }
	}


	return z;
}

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