Submission #1220075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220075		brinton	Dungeons Game (IOI21_dungeons)	C++20	0 / 100	69 ms	43320 KiB

dungeons

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

vector<int> s,p,w,l;
int N;
vector<vector<pair<long long,int>>> lj;//lj[k][start] after 2^k play, {earn_hero,nxt};
vector<vector<pair<long long,int>>> minStart;// minStart[k][start] after 2^k play, {min(s[i]-earn_hero,nxt)}
vector<long long> toN;// winning to N if all wins;
int alwaysWin = 0;
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<pair<long long,int>>(N));// atmost lost 2^24 times;
	minStart = vector(25,vector<pair<long long,int>>(N));// atmost lost 2^24 times;
	for(int i = 0;i < N;i++){
		lj[0][i].first = p[i];
		lj[0][i].second = l[i];

		minStart[0][i].first = s[i];
		minStart[0][i].second = l[i];
	}
	for(int k = 1;k < 25;k++){
		for(int i = 0;i < N;i++){
			auto [earn_hero,nxt] = lj[k-1][i];
			auto [earn_hero2,nxt2] = lj[k-1][nxt];
			lj[k][i] = {earn_hero+earn_hero2,nxt2};
			// auto [minz,m_nxt] = minStart[k-1][i];
			// auto [minz2,m_nxt2] = minStart[k-1][m_nxt];
			// // assert(nxt == m_nxt && nxt2 == m_nxt2);
			// minStart[k][i] = {min(minz,minz2-earn_hero),m_nxt2};
		}
	}

	// for(auto &i:s) alwaysWin = max(alwaysWin,i);
	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;
	
	// while(hero < alwaysWin && cur != N){
		for(int k = 24;k >= 0;k--){
			// auto [minz,nxt] = minStart[k][cur];
			auto [earn_hero,_nxt] = lj[k][cur];
			if(hero+earn_hero < s[0]) {
				// cout << "(" << k << " " << cur << "):" << minz << " " << hero << " " << nxt << endl;
				hero += earn_hero;
				cur = _nxt;
			}
		}
		if(hero < s[0]){
			hero += p[cur];
			cur = l[cur];
		}
		// must win here;
		// hero += s[cur];
		// cur = w[cur];
		// cout << "!" << hero << " " << cur << endl;
	// 	break;
	// }

	// for(auto &i:toN) cout << i << " ";cout << "toN" << endl;
	hero += toN[cur];
	return hero;
}

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