oj.uz

Submission #928066

# Submission time Handle Problem Language Result Execution time Memory
928066 2024-02-15T19:59:37 Z bobbilyking Dungeons Game (IOI21_dungeons) C++17
11 / 100
 36 ms 34772 KB 
#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.K;
        lift[i][0] = {edge.V, edge.V};
    }
    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;

    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 (z < thresh) {
        //         x = par[x][l];
        //         z += sm;

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

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 35 ms 34772 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 36 ms 34772 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 13404 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 13400 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 13400 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 13400 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 13404 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -