Submission #1179547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179547		Gr1sen	Dungeons Game (IOI21_dungeons)	C++20	11 / 100	7093 ms	33524 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include<iomanip>
#include<algorithm>

using namespace std;

#define ll long long
#define vi vector<int>
#define vl vector<ll>

int n;
vi S, P, W, L;
vl M, M2, M3;

ll oinkoink(int p) {
	if (p == n) return 0;
	if (M[p] != -1) return M[p];
	return M[p] = oinkoink(W[p]) + 1;
}

ll oinkoinkoink(int p, ll z) {
	if (p == n) return -1;
	if (M2[p] != -1) return -1;
	if (M3[p] != -1) {
		return M2[p] = z - M3[p];
	}
	M3[p] = z;
	ll a = oinkoinkoink(L[p], z + P[p]);
	if (a == -1) return -1;
	if (M2[p] != -1) return -1;
	M2[p] = a;
	return a;
}

void init(int N, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	n = N;
	S = s;
	P = p;
	W = w;
	L = l;
	M = vl(n, -1);
	M2 = vl(n, -1);
	M3 = vl(n, -1);
	for (int i = 0; i < n; i++) oinkoink(i);
	for (int i = 0; i < n; i++) oinkoinkoink(i, 0);
	return;
}


ll oink(int x, int z) {
	if (z >= S[0]) return M[x]*S[0];
	if (M2[x] == -1) return oink(L[x], z+P[x]);
	z += ((S[0]-z-1)/M[x])*M[x];
	return oink(L[x], z + P[x]);
}

long long simulate(int x, int z) {
	while (x != n) {
		if (S[x] <= z) {
			z += S[x];
			x = W[x];
			continue;
		}
		z += P[x];
		x = L[x];
	}
	return z;
}

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