제출 #1108195

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1108195		pit4h	던전 (IOI21_dungeons)	C++17	36 / 100	264 ms	238664 KiB

dungeons

#include "dungeons.h"

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

using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pi>;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i= (a); i < (b); i++)
#define per(i,a,b) for(int i = (b) - 1; i >= (a); i--)

#ifdef LOCAL
template<class A, class B> auto& operator<<(auto &o, pair<A, B> p) { return o << '(' << p.x << ", " << p.y << ')'; }
auto& operator<<(auto& o, auto a) {
	o << "{";
	for (auto b : a) o << b << ", ";
	return o << "}";
}
void dump(auto... x) { ((cerr << x << ", "), ...) << "\n"; }
#define debug(x...) cerr << "[" #x "]: ", dump(x)
#else
#define debug(...) ;
#endif

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int MAXN = 5e4 + 5, LOGZ = 25, DIV = 8;
const ll INF = 1e18 + 1;

int n;
vi s,p,w,l;

int dest[MAXN][LOGZ / DIV + 1][LOGZ];
ll gain[MAXN][LOGZ / DIV + 1][LOGZ], min_req[MAXN][LOGZ / DIV + 1][LOGZ];

void init(int _n, vi _s, vi _p, vi _w, vi _l) {
	n = _n; s = _s, p = _p, w = _w, l = _l;

	rep(t,0,LOGZ / DIV + 1) {
		int threshold = 1;
		rep(it,0,DIV) threshold = threshold * (1 << t);

		rep(i,0,n) {
			dest[i][t][0] = (s[i] <= threshold? w[i]:l[i]);
			gain[i][t][0] = (s[i] <= threshold? s[i]:p[i]); 
			min_req[i][t][0] = (s[i] <= threshold? INF:s[i]);
		}
		dest[n][t][0] = n;
		gain[n][t][0] = 0;
		min_req[n][t][0] = 0;

		rep(j,1,LOGZ) {
			rep(i,0,n) {
				int k = dest[i][t][j-1];
				dest[i][t][j] = dest[k][t][j-1];
				gain[i][t][j] = gain[k][t][j-1] + gain[i][t][j-1];
				ll tmp = min_req[k][t][j-1] - gain[i][t][j-1];
				min_req[i][t][j] = min(min_req[i][t][j-1], tmp);
			}
			dest[n][t][j] = n;
			gain[n][t][j] = 0;
			min_req[n][t][j] = 0;
		}
	}

	return;
}

ll simulate(int x, int z) {
	ll strength = z;
	debug("start", x, strength);
	rep(t,0,LOGZ / DIV + 1) {
		rep(it,0,DIV) {
			per(j,0,LOGZ) {
				if (min_req[x][t][j] > strength) {
					strength += gain[x][t][j];
					x = dest[x][t][j];	
					debug("jump", t, j, x, strength);
				}
			}
			if (x == n) break;
			debug("from", t, x, strength, s[x], p[x], w[x], l[x]);
			assert(s[x] <= strength);
			strength += s[x];
			x = w[x];
			debug("to", x, strength);	
			if (x == n) break;
		}
		if (x == n) break;
	}
	assert(x == n);
	return strength;
}

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