Submission #928102

#	Time	Username	Problem	Language	Result	Execution time	Memory
928102		bobbilyking	Dungeons Game (IOI21_dungeons)	C++17	24 / 100	7035 ms	276768 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 = 5e4+10;
const ll NN = 4e5+10;
// 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 = min(2*INF, 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) {
        if (s[i] > SN) {
            par[i][0] = l[i];
            lift[i][0] = {s[i], p[i]};
        } else {
            // when strength > SN, we always win here, so fix these to be winning edge. 
            par[i][0] = w[i];
            lift[i][1] = {s[i], s[i]};
        } 
    }
    F(i, 0, L) lift[n][i] = {-INF, 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;

    ll moves = 0;

    auto iterate1 = [&]{
        if (z >= s[x]) {
            // cout << "ADDED UP " << s[x] << endl;
            z += s[x], x = w[x];
        }
        else {
            // cout << "ADDED DOWN " << p[x] << endl;
            z += p[x], x = l[x];
        }

        ++moves;
    };

    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.
        // if (0)
        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;
            // }

            // cout << z << " " << thresh << " " << sm << endl;
            if (z < thresh ) {
                x = par[x][l];
                z += sm;

                // cout << "Jumped " << l << endl;
                moves += 1<<l;
            }
        }

        // cout << "WTF U ON " << moves << endl;

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

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