Submission #466881

#	Time	Username	Problem	Language	Result	Execution time	Memory
466881		alexxela12345	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	2260 ms	2097156 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <cassert>

using namespace std;

typedef long long ll;

const ll INF = 1e18;

const int B = 4;
const int LG = 30;

struct mdata {
    int v;
    ll  mxdelta, gained;
};

mdata merge(const mdata &a, const mdata &b) {
    return {b.v, max(a.mxdelta, b.mxdelta + a.gained), a.gained + b.gained};
}

int n;
vector<int> s, p, w, l;
vector<vector<vector<mdata>>> up;

void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_) {
    n = n_ + 1;
    s = s_;
    s.push_back(0);
    p = p_;
    p.push_back(0);
    w = w_;
    w.push_back(n - 1);
    l = l_;
    l.push_back(n - 1);
    up.resize(LG / B + 1, vector<vector<mdata>> (n, vector<mdata> (LG)));
    for (int i = 0; i * B < LG; i++) {
        int k = 1 << (i * B);
        for (int v = 0; v < n; v++) {
            if (s[v] < k) {
                up[i][v][0] = {w[v], -INF, s[v]};
            } else {
                up[i][v][0] = {l[v], -s[v], p[v]};
            }
        }
        for (int j = 1; j < LG; j++) {
            for (int v = 0; v < n; v++) {
                up[i][v][j] = merge(up[i][v][j - 1], up[i][up[i][v][j - 1].v][j - 1]);
            }
        }
    }
}

ll simulate(int v, int z_) {
    ll z = z_;
    int k = 0;
    while (v != n - 1) {
        while (k < LG / B && (1 << ((k + 1) * B)) <= z) {
            k++;
        }
        for (int i = LG - 1; i >= 0; i--) {
            if (z + up[k][v][i].mxdelta < 0) {
                z += up[k][v][i].gained;
                v = up[k][v][i].v;
            }
        }
        assert(z >= s[v]);
        z += s[v];
        v = w[v];
    }
    return z;
}

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