Submission #579840

#	Time	Username	Problem	Language	Result	Execution time	Memory
579840		joelau	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	2 ms	1236 KiB

dungeons

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

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

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
	N = n;
	for (int 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 (int k = 1; k < 25; ++k) for (int i = 0; i <= N; ++i) {
		if (lose[i][k-1] == make_pair(-1,-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(-1,-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 (int k = 24; k >= 0; --k)
		if (lose[x][k] != make_pair(-1,-1ll) && ans+lose[x][k].second < S[0])
			ans += lose[x][k].second, x = lose[x][k].first;
	ans += lose[x][0].second, x = lose[x][0].first;
	for (int k = 24; k >= 0; --k)
		if (win[x][k] != make_pair(-1,-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