Submission #1220117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220117		brinton	Dungeons Game (IOI21_dungeons)	C++20	63 / 100	2744 ms	2162688 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> s,p,w,l;
int N;
vector<vector<vector<pair<long long,int>>>> lj;
vector<vector<vector<long long>>> minStart;
/*
lj[h][k][start] after 2^k play, {earn_hero,nxt};, if __lg(hero) == h;
minStart[h][k][start] after 2^k play, {earn_hero,nxt};, if __lg(hero) == h;
*/
vector<long long> toN;
void init(int i_n, vector<int> i_s, vector<int> i_p, vector<int> i_w, vector<int> i_l) {
	N = i_n;
	s = i_s, p = i_p, w = i_w, l = i_l;
	lj = vector(25,vector(25,vector<pair<long long,int>>(N+1)));// atmost lost 2^24 times;
	minStart = vector(25,vector(25,vector<long long>(N+1)));

	vector<int> layer(N);
	for(int i = 0;i < N;i++) layer[i] = __lg(s[i]);
	// for(auto &i:layer) cout << i << " ";cout << "?!" << endl;
	for(int h = 0;h < 25;h++){// hero layer
		for(int i = 0;i < N;i++){
			if(layer[i] < h){
				lj[h][0][i].first = s[i];
				lj[h][0][i].second = w[i];
			}else if(layer[i] >= h){// lose, assume equal will lose(avoid using minStart)
				lj[h][0][i].first = p[i];
				lj[h][0][i].second = l[i];
			}
			if(layer[i] == h){// only care about equal
				minStart[h][0][i] = s[i];
			}else{
				minStart[h][0][i] = LLONG_MAX; 
			}
		}
		lj[h][0][N] = {0,N};
		minStart[h][0][N] = 0;
		for(int k = 1;k < 25;k++){
			for(int i = 0;i <= N;i++){
				auto [earn_hero,nxt] = lj[h][k-1][i];
				auto [earn_hero2,nxt2] = lj[h][k-1][nxt];
				lj[h][k][i] = {earn_hero+earn_hero2,nxt2};
				auto minz = minStart[h][k-1][i];
				auto minz2 = minStart[h][k-1][nxt];
				minStart[h][k][i] = min(minz,minz2-earn_hero);
			}
		}

	}
	toN = vector<long long>(N+1,0);
	for(int i = N-1;i >= 0;i--){
		toN[i] = toN[w[i]]+s[i];
	}
}

long long simulate(int x, int z) {
	int cur = x;
	long long hero = z;
	
	
	for(int h = 0;h < 25;h++){
		if(__lg(hero) > h) continue;// hero not in this layer;
		// if(__lg(hero) < h){
		// 	cout << "error:" << h << endl;
		// 	break;
		// }
		// cout << "!" << h << ":" << hero << " " << cur << endl;
		for(int k = 24;k >= 0;k--){
			auto [earn_hero,nxt] = lj[h][k][cur];
			auto minz = minStart[h][k][cur];
			if(nxt == N) continue;
			// if(hero+earn_hero < (1 << (h+1)) && hero >= minz) {
			// 	cout << "win on layer(" << k << "):" << nxt << " " << hero << " " << earn_hero << " " << minz << endl;
			// }
			if(hero+earn_hero < (1 << (h+1)) && hero < minz) {// if do not meet 2^(h+1) and actually lose
				hero += earn_hero;
				cur = nxt;
				// cout << "(" <<h << "," << k << ") : " << hero << " " << cur << endl;
			}
		}
		if(hero < s[cur]){
			hero += p[cur];
			cur = l[cur];
		}
		// must win here;
		if(cur == N) return hero;
		if(hero >= s[cur]){
			hero += s[cur];
			cur = w[cur];
		}
		if(cur == N) return hero;
	}

	hero += toN[cur];
	return hero;
}

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