Submission #600300

#	Time	Username	Problem	Language	Result	Execution time	Memory
600300		Jarif_Rahman	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7064 ms	403728 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const int K = 43;
const ll inf = 1e18;

int n;
vector<int> S, P, W, L;

int* jump[K];
ll* sum[K];
ll* dp[K];

int msb(ll x){
    return 63-__builtin_clzll(x);
}

pair<int, ll> binlift(int nd, ll s){
    if(nd == n) return {nd, s};
    if(s <= dp[msb(s)][nd]) return binlift(jump[msb(s)][nd], s+sum[msb(s)][nd]);
    else if(s >= S[nd]) return binlift(W[nd], s+S[nd]);
    else return binlift(L[nd], s+P[nd]);
}

void init(int _n, vector<int> _S, vector<int> _P, vector<int> _W, vector<int> _L){
    n = _n, S = _S, P = _P, W = _W, L = _L;

    S.pb(0);
    P.pb(0);

    for(int k = 0; k < K; k++){
        jump[k] = new int[n+1];
        sum[k] = new ll[n+1];
        dp[k] = new ll[n+1];

        fill(jump[k], jump[k]+n+1, n);
        fill(sum[k], sum[k]+n+1, 0);
        fill(dp[k], dp[k]+n+1, 0);
    }

    vector<int> state(n+1, 0);
    vector<int> jumpd(n+1, 0);

    function<void(int, int)> create_pointers = [&](int k, int nd){
        int p;
        ll sm, _dp;
        if(S[nd] <= (1LL<<k)){
            p = W[nd];
            sm = S[nd];
            _dp = inf;
        }
        else{
            p = L[nd];
            sm = P[nd];
            _dp = S[nd]-1;
        }
        state[nd] = 1;
        if(state[p] != 2){
            if(!state[p]) create_pointers(k, p);
            else{
                jump[k][nd] = p;
                sum[k][nd] = sm;
                dp[k][nd] = _dp;
                jumpd[nd] = 1;
                state[nd] = 2;
                return;
            }
        }
        if(jumpd[p] == jumpd[jump[k][p]]){
            jump[k][nd] = jump[k][jump[k][p]];
            jumpd[nd] = jumpd[p]+jumpd[jump[k][p]]+1;
            sum[k][nd] = sum[k][p]+sum[k][jump[k][p]]+sm;
            dp[k][nd] = min(_dp, min(dp[k][p]-sm, dp[k][jump[k][p]]-sm-sum[k][p]));
        }
        else{
            jump[k][nd] = p;
            sum[k][nd] = sm;
            dp[k][nd] = _dp;
            jumpd[nd] = 1;
        }
        state[nd] = 2;
    };

    for(int k = 0; k < K; k++){
        state.assign(n+1, 0);
        jumpd.assign(n+1, 0);
        state[n] = 2;
        create_pointers(k, 0);
    }
}

ll simulate(int x, int z){
    return binlift(x, z).sc;
}

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