Submission #928076

#	Time	Username	Problem	Language	Result	Execution time	Memory
928076		bobbilyking	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	1550 ms	68660 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
#define A(a) (a).begin(), (a).end()
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define F(i, l, r) for (ll i = (l); i < (r); ++i)
#define FD(i, l, r) for (ll i = (l); i > (r); --i)
#define K first
#define V second

const ll NN = 50010;
// const ll SN = 0;
const ll SN = 3200;

ll n;

ll s[NN], p[NN], w[NN], l[NN];

// We need this, because this lets us win fast. Otherwise ,would  take O(n) even when strength >> 1e7
pl ans[NN]; // {minimum strength needed to clear to root, bonus delta }


using T = pl;
const ll L = 26;
pl lift[NN][L];
ll par[NN][L];

constexpr ll INF = 1e18;

T f(T a, T b) {
    T res;
    res.K = min(a.K, b.K - a.V);
    res.V = a.V + b.V;
    return res;
}

void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
    n = _n;
    copy(A(_s), s);
    copy(A(_p), p);
    copy(A(_w), w);
    copy(A(_l), l);

    // precomp ans
    FD(i, n-1, -1) {
        ans[i].K = max(s[i], ans[w[i]].K - s[i]);   
        ans[i].V = ans[w[i]].V + s[i];
    }

    F(i, 0, n) {
        pl edge;
        if (s[i] > SN) edge = {p[i], l[i]};
        else edge = {s[i], w[i]};

        par[i][0] = edge.V;
        lift[i][0] = {s[i], edge.K};
    }
    F(i, 0, L) lift[n][i] = {1e18, 0};

    F(l, 1, L) F(i, 0, n) {
        par[i][l] = par[par[i][l-1]][l-1];
        lift[i][l] = f(lift[i][l-1], lift[par[i][l-1]][l-1]);
    }

    // F(i, 0, n) {
    //     F(l, 0, L) cout << lift[i][l].K << " " << lift[i][l].V << " | ";
    //     cout << endl;
    // }

}

long long simulate(int _x, int _z) {
    ll x = _x, z = _z;

    auto iterate1 = [&]{
        if (z >= s[x]) z += s[x], x = w[x];
        else z += p[x], x = l[x];
    };

    while (x != n and z <= SN) {
        iterate1();
    }

    if (x == n) return z;

    // TODO: implement some kind of bsearch dictating how far to go while taking
    // only "losing" edges

    // cout << "Currently: " << x << " " << z << endl;

    while (1) {    
        if (ans[x].K <= z) return ans[x].V + z;
        // cout << "Started with " << x << " " << z << endl;
        // figure out where to jump, then update x and z. We are now at a winning node.
        FD(l, L-1, -1) {
            const auto &[thresh, sm] = lift[x][l];

            // if (l == 1) {
            //     cout << "Why not jump here? " << endl;
            //     cout << thresh << " " << sm << " | " << z << endl;

            //     auto [a1, b1] = lift[0][0];
            //     auto [a2, b2] = lift[1][0];
                
            //     cout << a1 << " " << b1 << " " << a2 << " " << b2 << endl;
            // }
            if (z < thresh) {
                x = par[x][l];
                z += sm;

                // cout << "Jumped " << l << endl;
            }
        }

        if (x == n) return z;
        // iterate1();
        // cout << "WTF " << x << " " << z << " " << s[x] << endl;
        assert(s[x] > SN and z >= s[x]); 
        iterate1(); 
    }
}

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