Submission #600206

#	Time	Username	Problem	Language	Result	Execution time	Memory
600206		Jarif_Rahman	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	5221 ms	1371116 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 K1 = 19, K2 = 9;
const ll inf = 1e18;

ll p5[35];

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

int* nxt[K1][K2];
ll* sum[K1][K2];
ll* dp[K1][K2];

int msb(ll x){
    return floor(log(x)/log(5));
}

pair<int, ll> binlift(int nd, ll s){
    if(s > dp[msb(s)][0][nd]) return {nd, s};
    for(int i = K2-1; i >= 0; i--) if(s <= dp[msb(s)][i][nd])
        return binlift(nxt[msb(s)][i][nd], s+sum[msb(s)][i][nd]);
    return {-1, -1};
}

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);

    p5[0] = 1;
    for(int i = 1; i < 25; i++) p5[i] = p5[i-1]*5;

    for(int j = 0; j < K1; j++) for(int k = 0; k < K2; k++){
        nxt[j][k] = new int[n+1];
        sum[j][k] = new ll[n+1];
        dp[j][k] = new ll[n+1];

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

    for(int k = 0; k < K1; k++) for(int i = 0; i < n; i++){
        if(S[i] <= p5[k]){
            nxt[k][0][i] = W[i];
            sum[k][0][i] = S[i];
            dp[k][0][i] = inf;
        }
        else{
            nxt[k][0][i] = L[i];
            sum[k][0][i] = P[i];
            dp[k][0][i] = S[i]-1;
        }
    }

    for(int k = 0; k < K1; k++){
        for(int p = 1; p < K2; p++) for(int i = 0; i <= n; i++){
            nxt[k][p][i] = nxt[k][p-1][nxt[k][p-1][nxt[k][p-1][nxt[k][p-1][nxt[k][p-1][i]]]]];

            sum[k][p][i] = sum[k][p-1][i]+sum[k][p-1][nxt[k][p-1][i]]+
                sum[k][p-1][nxt[k][p-1][nxt[k][p-1][i]]] +
                sum[k][p-1][nxt[k][p-1][nxt[k][p-1][nxt[k][p-1][i]]]] +
                sum[k][p-1][nxt[k][p-1][nxt[k][p-1][nxt[k][p-1][nxt[k][p-1][i]]]]];

            dp[k][p][i] = min(dp[k][p-1][i],
                min(dp[k][p-1][nxt[k][p-1][i]]-sum[k][p-1][i],
                min(
                dp[k][p-1][nxt[k][p-1][nxt[k][p-1][i]]]-sum[k][p-1][i]-sum[k][p-1][nxt[k][p-1][i]],
                min(
                dp[k][p-1][nxt[k][p-1][nxt[k][p-1][nxt[k][p-1][i]]]]-sum[k][p-1][i]
                -sum[k][p-1][nxt[k][p-1][i]]-
                sum[k][p-1][nxt[k][p-1][nxt[k][p-1][i]]],

                dp[k][p-1][nxt[k][p-1][nxt[k][p-1][nxt[k][p-1][nxt[k][p-1][i]]]]]
                -sum[k][p-1][i]-sum[k][p-1][nxt[k][p-1][i]]-
                sum[k][p-1][nxt[k][p-1][nxt[k][p-1][i]]]-
                sum[k][p-1][nxt[k][p-1][nxt[k][p-1][nxt[k][p-1][i]]]]
                ))));
        }
    }
}

ll simulate(int x, int z){
    ll s = z;

    while(x != n){
        tie(x, s) = binlift(x, s);
        if(x == n) break;
        if(s >= S[x]) s+=S[x], x = W[x];
        else s+=P[x], x = L[x];
    }

    return s;
}

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