oj.uz

Submission #928109

# Submission time Handle Problem Language Result Execution time Memory
928109 2024-02-15T20:49:31 Z bobbilyking Dungeons Game (IOI21_dungeons) C++17
24 / 100
 7000 ms 35928 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 = 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 = max(-INF, 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)

        if (s[x] >= SN and z > s[x]) {
            iterate1(); continue;
        }
        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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 30 ms 34752 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 30 ms 34652 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Runtime error 135 ms 28216 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 46 ms 35596 KB Output is correct
3 Correct 48 ms 35676 KB Output is correct
4 Correct 57 ms 35928 KB Output is correct
5 Correct 40 ms 35672 KB Output is correct
6 Correct 62 ms 35676 KB Output is correct
7 Correct 235 ms 35672 KB Output is correct
8 Correct 55 ms 35412 KB Output is correct
9 Correct 45 ms 35676 KB Output is correct
10 Correct 105 ms 35928 KB Output is correct
11 Correct 1578 ms 35928 KB Output is correct
12 Correct 1678 ms 35928 KB Output is correct
13 Correct 422 ms 35664 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 46 ms 35596 KB Output is correct
3 Correct 48 ms 35676 KB Output is correct
4 Correct 57 ms 35928 KB Output is correct
5 Correct 40 ms 35672 KB Output is correct
6 Correct 62 ms 35676 KB Output is correct
7 Correct 235 ms 35672 KB Output is correct
8 Correct 55 ms 35412 KB Output is correct
9 Correct 45 ms 35676 KB Output is correct
10 Correct 105 ms 35928 KB Output is correct
11 Correct 1578 ms 35928 KB Output is correct
12 Correct 1678 ms 35928 KB Output is correct
13 Correct 422 ms 35664 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 691 ms 35684 KB Output is correct
16 Correct 51 ms 35676 KB Output is correct
17 Correct 44 ms 35676 KB Output is correct
18 Correct 2239 ms 35680 KB Output is correct
19 Correct 67 ms 35672 KB Output is correct
20 Correct 158 ms 35676 KB Output is correct
21 Correct 1494 ms 35552 KB Output is correct
22 Execution timed out 7024 ms 35676 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 46 ms 35596 KB Output is correct
3 Correct 48 ms 35676 KB Output is correct
4 Correct 57 ms 35928 KB Output is correct
5 Correct 40 ms 35672 KB Output is correct
6 Correct 62 ms 35676 KB Output is correct
7 Correct 235 ms 35672 KB Output is correct
8 Correct 55 ms 35412 KB Output is correct
9 Correct 45 ms 35676 KB Output is correct
10 Correct 105 ms 35928 KB Output is correct
11 Correct 1578 ms 35928 KB Output is correct
12 Correct 1678 ms 35928 KB Output is correct
13 Correct 422 ms 35664 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 691 ms 35684 KB Output is correct
16 Correct 51 ms 35676 KB Output is correct
17 Correct 44 ms 35676 KB Output is correct
18 Correct 2239 ms 35680 KB Output is correct
19 Correct 67 ms 35672 KB Output is correct
20 Correct 158 ms 35676 KB Output is correct
21 Correct 1494 ms 35552 KB Output is correct
22 Execution timed out 7024 ms 35676 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Runtime error 135 ms 28216 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -