Submission #437448

#	Time	Username	Problem	Language	Result	Execution time	Memory
437448		maomao90	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	7033 ms	36916 KiB

dungeons

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

#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)

template <class T>
inline void mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline void mxto(T& a, T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;

#ifdef DEBUG
#define debug(args...) _debug(args)
inline void _debug(const char* format, ...) {
	va_list args;
	va_start(args, format);
	vprintf(format, args);
	va_end(args);
}
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MAXN 400005
#define MAXL 30

int n;
vi s, w, l, v;
vll p, r;

bool visited[MAXN];
vi topo;
void getTopo(int u) {
	if (!visited[w[u]]) {
		visited[w[u]] = 1;
		getTopo(w[u]);
	}
	topo.pb(u);
}
void getTopo1(int u) {
	if (!visited[l[u]]) {
		visited[l[u]] = 1;
		getTopo1(l[u]);
	}
	topo.pb(u);
}

void init(int _n, vi _s, vi _p, vi _w, vi _l) {
	n = _n; s = _s, w = _w, l = _l;
	s.pb(0);
	_p.pb(0);
	w.pb(n);
	l.pb(n);
	REP (i, 0, n + 1) {
		r.pb(s[i]);
		p.pb(_p[i]);
	}
	REP (i, 0, n) {
		if (!visited[i]) {
			visited[i] = 1;
			getTopo(i);
		}
	}
	for (int &i : topo) {
		if (i == n) continue;
		if (s[w[i]] <= r[i] + s[i]) {
			r[i] += r[w[i]];
			w[i] = w[w[i]];
		}
		debug("%d: %d %lld\n", i, w[i], r[i]);
	}
	topo.clear();
	REP (i, 0, n) {
		if (!visited[i]) {
			visited[i] = 1;
			getTopo1(i);
		}
	}
	REP (k, 0, 100) {
		for (int &i : topo) {
			if (s[l[i]] >= s[i] + p[i]) {
				p[i] += p[l[i]];
				l[i] = l[l[i]];
			}
		}
	}
}

ll simulate(int x, int z) {
	ll ans = z;
	while (x != n) {
		if (ans >= s[x]) {
			ans += r[x];
			x = w[x];
		} else {
			ans += p[x];
			x = l[x];
		}
	}
	return ans;
}

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