Submission #599022

#	Time	Username	Problem	Language	Result	Execution time	Memory
599022		Jarif_Rahman	Dungeons Game (IOI21_dungeons)	C++17	50 / 100	7014 ms	387684 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 KU = 21, KD = 25;

const ll inf = 1.5e17;

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

vector<int> ancU[KU];
vector<ll> sumU[KU];
vector<ll> dpU[KU];

vector<int> ancD[KD];
vector<ll> sumD[KD];
vector<ll> dpD[KD];

pair<int, ll> binliftUp(int nd, ll s){
    if(nd == n || s < S[nd]) return {nd, s};
    for(int i = KU-1; i >= 0; i--){
        if(s >= dpU[i][nd]) return binliftUp(ancU[i][nd], s+sumU[i][nd]);
    }
    return {-1, -1};
}

pair<int, ll> binliftDown(int nd, ll s){
    if(nd == n || s >= S[nd]) return {nd, s};
    for(int i = KD-1; i >= 0; i--){
        if(s <= dpD[i][nd]) return binliftDown(ancD[i][nd], s+sumD[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);

    fill(ancU, ancU+KU, vector<int>(n+1, n));
    fill(sumU, sumU+KU, vector<ll>(n+1, 0));
    fill(dpU, dpU+KU, vector<ll>(n+1, 0));    

    for(int i = 0; i < n; i++){
        ancU[0][i] = W[i];
        sumU[0][i] = S[i];
        dpU[0][i] = S[i];
    }

    for(int p = 1; p < KU; p++) for(int i = 0; i <= n; i++){
        ancU[p][i] = ancU[p-1][ancU[p-1][i]];
        sumU[p][i] = sumU[p-1][i]+sumU[p-1][ancU[p-1][i]];
        dpU[p][i] = max(dpU[p-1][i], dpU[p-1][ancU[p-1][i]]-sumU[p-1][i]);
    }

    fill(ancD, ancD+KD, vector<int>(n+1, n));
    fill(sumD, sumD+KD, vector<ll>(n+1, 0));
    fill(dpD, dpD+KD, vector<ll>(n+1, inf));

    for(int i = 0; i < n; i++){
        ancD[0][i] = L[i];
        sumD[0][i] = P[i];
        dpD[0][i] = S[i]-1;
    }

    for(int p = 1; p < KD; p++) for(int i = 0; i <= n; i++){
        ancD[p][i] = ancD[p-1][ancD[p-1][i]];
        sumD[p][i] = sumD[p-1][i]+sumD[p-1][ancD[p-1][i]];
        dpD[p][i] = min(dpD[p-1][i], dpD[p-1][ancD[p-1][i]]-sumD[p-1][i]);
    }
}

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

    while(x != n){
        tie(x, s) = binliftUp(x, s);
        if(x == n) break;
        tie(x, s) = binliftDown(x, s);
    }

    return s;
}

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