Submission #583521

#	Time	Username	Problem	Language	Result	Execution time	Memory
583521		PiejanVDC	Dungeons Game (IOI21_dungeons)	C++17	26 / 100	658 ms	175544 KiB

dungeons

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

using namespace std;

const int mxN = (int)4e5 + 5;

int lim[mxN][32];
int jump[mxN][32];
int gget[mxN][32];

vector<int>L,S;
int N;

void init(int n, vector<int>s, vector<int>p, vector<int>w, vector<int>l) {
    L = l;
    S = s;
    N = n;
    for(int i = 0 ; i < n ; i++) {
        jump[i][0] = w[i];
        lim[i][0] = s[i];
        gget[i][0] = s[i];
    }
    jump[n][0] = n;
    for(int j = 1 ; j <= 30 ; j++) {
        for(int i = 0 ; i <= n ; i++) {
            jump[i][j] = jump[jump[i][j-1]][j-1];
            lim[i][j] = max(lim[i][j-1], lim[jump[i][j-1]][j-1] - gget[i][j-1]);
            gget[i][j] = gget[i][j-1] + gget[jump[i][j-1]][j-1];
        }
    }
}

long long simulate(int x, int z) {
    long long ans = z;

    while(x != N) {
        for(int j = 30 ; j >= 0 ; j--) {
            if(jump[x][j] != N && ans >= lim[x][j]) {
                ans += gget[x][j];
                x = jump[x][j];
            }
        }
        if(x != N) {
            if(lim[x][0] <= ans) {
                ans += S[x];
                x = jump[x][0];
            } else {
                ans += S[x];
                x = L[x];
            }
        }
    }

    return ans;
}

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