Submission #441785

#	Time	Username	Problem	Language	Result	Execution time	Memory
441785		fleimgruber	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	576 ms	254660 KiB

dungeons

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

using namespace std;

const int MAX_N = 400001;
const int MAX_LOG = 25; // 2^24 > 10^7

int n, p[MAX_N], l[MAX_N];
struct {
	int end;
	long long gained;
	long long min; // min(sum(gained) - opponent)
} dp[MAX_N][MAX_LOG];

void init(int n_, vector<int> s, vector<int> p_,
		vector<int> w, vector<int> l_) {
	n = n_;
	copy_n(p_.begin(), n, p);
	copy_n(l_.begin(), n, l);
	l[n] = n;
	for (int j = 0; j < MAX_LOG; j++)
		for (int i = 0; i <= n; i++) {
			auto& x = dp[i][j];
			if (j == 0)
				if (i == n) {
					x.end = n;
					x.gained = x.min = 0;
				} else {
					x.end = w[i];
					x.gained = s[i];
					x.min = -s[i];
				}
			else {
				auto& a = dp[i][j - 1];
				auto& b = dp[a.end][j - 1];
				x.end = b.end;
				x.gained = a.gained + b.gained;
				x.min = min(a.min, a.gained + b.min);
			}
		}
}

// because p[i] = s[i], every time we lose, our strength doubles
// => we only lose log(max(s)) times. use binary lifting to find next
//	  fight we lose
long long simulate(int at, int strength) {
	// do we lose any of the next 2^j fights?
	auto lose = [&](int j) {
		return strength + dp[at][j].min < 0;
	};
	while (at != n) {
		// jump until we lose
		for (int j = MAX_LOG - 1; j >= 0; j--)
			if (!lose(j)) {
				auto& x = dp[at][j];
				at = x.end;
				strength += x.gained;
			}
		// lose (if at = n, this adds 0)
		strength += p[at]; // = s[at] > strength
		at = l[at];
	}
	return strength;
}

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