제출 #1108180

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1108180		pit4h	던전 (IOI21_dungeons)	C++17	63 / 100	1008 ms	1064384 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;
const ll INF = 1e18 + 1;

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

int dest[MAXN][LOGZ][LOGZ];
ll gain[MAXN][LOGZ][LOGZ], min_req[MAXN][LOGZ][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) {
		int 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) {
		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;
	}
	assert(x == n);
	return strength;
}

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