Submission #579851

#	Time	Username	Problem	Language	Result	Execution time	Memory
579851		joelau	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	4 ms	2260 KiB

dungeons

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

long long N, S[400005], P[400005], W[400005], L[400005];
pair<long long,long long> lose[400005][60], win[400005][60];

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
	N = n;
	for (long long i = 0; i < N; ++i)
		S[i] = s[i], P[i] = p[i], W[i] = w[i], L[i] = l[i], lose[i][0] = make_pair(L[i],P[i]), win[i][0] = make_pair(W[i],S[i]);
	lose[N][0] = win[N][0] = make_pair(-1,-1);
	for (long long k = 1; k < 60; ++k) for (long long i = 0; i <= N; ++i) {
		if (lose[i][k-1] == make_pair(-1ll,-1ll)) lose[i][k] = make_pair(-1,-1);
		else {
			lose[i][k].first = lose[lose[i][k-1].first][k-1].first;
			if (lose[i][k].first == -1) lose[i][k].second = -1;
			else lose[i][k].second = lose[i][k-1].second + lose[lose[i][k-1].first][k-1].second;
		}
		if (win[i][k-1] == make_pair(-1ll,-1ll)) win[i][k] = make_pair(-1,-1);
		else {
			win[i][k].first = win[win[i][k-1].first][k-1].first;
			if (win[i][k].first == -1) win[i][k].second = -1;
			else win[i][k].second = win[i][k-1].second + win[win[i][k-1].first][k-1].second;
		}
	}
}

long long simulate(int x, int z) {
	long long ans = z;
	for (long long k = 59; k >= 0; --k)
		if (lose[x][k] != make_pair(-1ll,-1ll) && ans+lose[x][k].second < S[0])
			ans += lose[x][k].second, x = lose[x][k].first;
	if (ans < S[0]) ans += lose[x][0].second, x = lose[x][0].first;
	for (long long k = 59; k >= 0; --k)
		if (win[x][k] != make_pair(-1ll,-1ll))
			ans += win[x][k].second, x = win[x][k].first;
	return ans;
}

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