Submission #491293

#	Time	Username	Problem	Language	Result	Execution time	Memory
491293		doowey	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3556 ms	1742292 KiB

dungeons

#include <bits/stdc++.h>
#include "dungeons.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int LOG3 = 9;
const int BASE = 8;
const int LOG2 = 25;
const int N = (int)4e5;
const ll inf = (ll)1e18;

ll gain[LOG3][LOG2][N];
ll lim[LOG3][LOG2][N];
int go[LOG3][LOG2][N];
vector<int> S, P, W, L;
ll B[LOG3];
int n;

void init(int _n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
	n = _n;
	B[0] = 1;
	for(int i = 1; i < LOG3; i ++ ){
        B[i] = B[i - 1] * BASE;
	}
	S = s;
	P = p;
	W = w;
	L = l;
	for(int C = 0; C < LOG3; C ++ ){
        for(int i = 0 ; i < n; i ++ ){
            if(S[i] < B[C]){
                if(w[i] == n){
                    go[C][0][i] = -1;
                }
                else{
                    go[C][0][i] = w[i];
                    gain[C][0][i] = S[i];
                    lim[C][0][i] = inf;
                }
            }
            else{
                if(l[i] == n){
                    go[C][0][i] = -1;
                }
                else{
                    go[C][0][i] = l[i];
                    gain[C][0][i] = p[i];
                    lim[C][0][i] = S[i];
                }
            }
        }
    }
    for(int C = 0 ; C < LOG3; C ++ ){
        for(int lg = 1; lg < LOG2; lg ++ ){
            for(int i = 0 ; i < n; i ++ ){
                if(go[C][lg-1][i] == -1 || go[C][lg-1][go[C][lg-1][i]] == -1){
                    go[C][lg][i] = -1;
                }
                else{
                    go[C][lg][i] = go[C][lg-1][go[C][lg-1][i]];
                    gain[C][lg][i] = gain[C][lg-1][i] + gain[C][lg-1][go[C][lg-1][i]];
                    lim[C][lg][i] = min(lim[C][lg-1][i], lim[C][lg-1][go[C][lg-1][i]] - gain[C][lg-1][i]);
                }
            }
        }
    }
	return;
}

ll simulate(int x, int Z) {
    ll strength = Z;
    int curb = 0;
    while(x != n){

        while(curb + 1 < LOG3 && B[curb + 1] <= strength){
            curb ++ ;
        }
        for(int lg = LOG2 - 1; lg >= 0 ; lg -- ){
            if(go[curb][lg][x] == -1) continue;
            if(strength >= lim[curb][lg][x]) continue;
            strength += gain[curb][lg][x];
            x = go[curb][lg][x];
        }

        if(strength >= S[x]){
            strength += S[x];
            x = W[x];
        }
        else{
            strength += P[x];
            x = L[x];
        }
        // one "special" manual move
    }
	return strength;
}

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