Submission #1057496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057496		Trent	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	111 ms	27572 KiB

dungeons

#include "dungeons.h"
#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
typedef long long ll;
typedef vector<int> vi;
int n;
vi s, p, w, l;

const int ME = 20;
vi skp;

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;
	skp.push_back(0);
	forR(i, ME) skp.push_back(1 << i);
}

struct pii{int a; ll b;};
int ops = 0;
pii tWin(int x, ll z, int ig) {
	assert(z >= ig);
	int ci=x; ll cv = z;
	while(ci != n && (s[ci] <= ig || cv < s[ci])) {
		++ops;
		assert(ops <= 6e6 + 10);
		if(s[ci] <= ig) cv += s[ci], ci = w[ci];
		else cv += p[ci], ci = l[ci];
	}
	return {ci, cv};
}
long long simulate(int x, int z) {
	int ci = x;
	ll cv = z;
	for(int sk : skp) {
		pii nex = tWin(ci, cv, sk);
		if(nex.a == n) {
			return nex.b;
		}
		ci=nex.a;
		cv=nex.b;
		assert(cv >= s[ci]);
		cv += s[ci];
		ci = w[ci];
	}
	return cv;
}

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