제출 #438276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
438276		JustasZ	던전 (IOI21_dungeons)	C++17	0 / 100	922 ms	1048580 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define rd() abs((int)rng())
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int LOG = 25;
vector<vector<vector<ll> > >sum(400001, vector<vector<ll> >(LOG));
vector<vector<vector<ll> > >mn(400001, vector<vector<ll> >(LOG));
vector<vector<vector<int> > >jump(400001, vector<vector<int> >(LOG));
int n;
vector<int>s, p, w, l;
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;

	for (int i = 0; i <= n; i++) {
		for (int grp = 0; grp < LOG; grp++) {
			sum[i][grp] = vector<ll>(grp + 1, 0);
			mn[i][grp] = vector<ll>(grp + 1, 1e18);
			jump[i][grp] = vector<int>(grp + 1, -1);
		}
	}

	for (int grp = 0; grp < LOG; grp++) {
		int upto = 1 << grp;
		vector<int>nodes;
		vector<int>in_grp(n + 1);
		for (int i = 0; i < n; i++) {
			if (s[i] <= upto || p[i] <= upto) {
				nodes.pb(i);
				in_grp[i] = 1;
			}
		}
		for (int jmp = 0; jmp < grp; jmp++) {
			for (int i : nodes) {
				if (jmp == 0) {
					int to;
					if (s[i] <= upto) {
						sum[i][grp][0] = s[i];
						to = w[i];
					} else {
						sum[i][grp][0] = p[i];
						mn[i][grp][0] = s[i];
						to = l[i];
					}

					jump[i][grp][0] = to;
				} else {
					int x = jump[i][grp][jmp - 1];
					if (x != -1 && in_grp[x]) {
						sum[i][grp][jmp] = sum[i][grp][jmp - 1] + sum[x][grp][jmp - 1];
						mn[i][grp][jmp] = min(mn[i][grp][jmp - 1], mn[x][grp][jmp - 1] - sum[i][grp][jmp - 1]);
						jump[i][grp][jmp] = jump[x][grp][jmp - 1];
					} else {
						jump[i][grp][jmp] = -1;
					}
				}
			}
		}
	}
}

ll simulate(int x, int z) {
	ll cur_sum = z;
	int cur = x;
	for (int grp = 0; grp < LOG - 1; grp++) {
		ll group_lower_bound = 1 << grp;
		if (cur_sum >= group_lower_bound * 2) {
			continue;
		}

		// if (cur_sum < group_lower_bound) {
		// 	exit(3);
		// }

		for (int jmp = grp; jmp >= 0; jmp--) {
			if (jump[cur][grp][jmp] == -1 
				|| (cur_sum + sum[cur][grp][jmp] >= group_lower_bound * 2)
				|| (cur_sum >= mn[cur][grp][jmp])) {
				continue;
			}
			cur_sum += sum[cur][grp][jmp];
			cur = jump[cur][grp][jmp];
		}

		if (cur == n) {
			return cur_sum;
		}

		// cout << cur << " " << cur_sum << " " << jump[cur][grp][0] << " " << sum[cur][grp][0] << " " << mn[cur][grp][0] << "\n";
		if (cur_sum >= s[cur]) {
			cur_sum += s[cur];
			cur = w[cur];
		} else {
			cur_sum += p[cur];
			cur = l[cur];
		}

		// if (grp != LOG - 1 && cur != n && cur_sum < group_lower_bound * 2) {
		// 	exit(3);
		// }

		// cout << "after finishing group " << grp << " we are at " << cur << " with strength " << cur_sum << "\n";
		if (cur == n) {
			return cur_sum;
		}
	}

	for (int jmp = LOG - 1; jmp >= 0; jmp--) {
		if (jump[cur][LOG - 1][jmp] != -1) {
			cur_sum += sum[cur][LOG - 1][jmp];
			cur = jump[cur][LOG - 1][jmp];
		}
	}

	if (cur == n) {
		return cur_sum;
	}
	
	if (cur_sum >= s[cur]) {
		cur_sum += s[cur];
		cur = w[cur];
	} else {
		cur_sum += p[cur];
		cur = l[cur];
	}

	return cur_sum;
}

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