oj.uz

Submission #928102

# Submission time Handle Problem Language Result Execution time Memory
928102 2024-02-15T20:45:29 Z bobbilyking Dungeons Game (IOI21_dungeons) C++17
24 / 100
 7000 ms 276768 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 = 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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 28 ms 47964 KB Output is correct
5 Correct 3 ms 12888 KB Output is correct
6 Correct 27 ms 47836 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Execution timed out 7035 ms 276768 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 47 ms 48728 KB Output is correct
3 Correct 52 ms 48736 KB Output is correct
4 Correct 41 ms 48728 KB Output is correct
5 Correct 42 ms 48616 KB Output is correct
6 Correct 60 ms 48732 KB Output is correct
7 Correct 198 ms 48728 KB Output is correct
8 Correct 64 ms 48732 KB Output is correct
9 Correct 43 ms 48732 KB Output is correct
10 Correct 105 ms 48536 KB Output is correct
11 Correct 1415 ms 48720 KB Output is correct
12 Correct 1468 ms 48732 KB Output is correct
13 Correct 405 ms 48720 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 47 ms 48728 KB Output is correct
3 Correct 52 ms 48736 KB Output is correct
4 Correct 41 ms 48728 KB Output is correct
5 Correct 42 ms 48616 KB Output is correct
6 Correct 60 ms 48732 KB Output is correct
7 Correct 198 ms 48728 KB Output is correct
8 Correct 64 ms 48732 KB Output is correct
9 Correct 43 ms 48732 KB Output is correct
10 Correct 105 ms 48536 KB Output is correct
11 Correct 1415 ms 48720 KB Output is correct
12 Correct 1468 ms 48732 KB Output is correct
13 Correct 405 ms 48720 KB Output is correct
14 Correct 2 ms 12888 KB Output is correct
15 Correct 695 ms 48768 KB Output is correct
16 Correct 54 ms 48732 KB Output is correct
17 Correct 44 ms 48732 KB Output is correct
18 Correct 2065 ms 48604 KB Output is correct
19 Correct 67 ms 48732 KB Output is correct
20 Correct 156 ms 48728 KB Output is correct
21 Correct 1375 ms 48984 KB Output is correct
22 Execution timed out 7023 ms 48720 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 47 ms 48728 KB Output is correct
3 Correct 52 ms 48736 KB Output is correct
4 Correct 41 ms 48728 KB Output is correct
5 Correct 42 ms 48616 KB Output is correct
6 Correct 60 ms 48732 KB Output is correct
7 Correct 198 ms 48728 KB Output is correct
8 Correct 64 ms 48732 KB Output is correct
9 Correct 43 ms 48732 KB Output is correct
10 Correct 105 ms 48536 KB Output is correct
11 Correct 1415 ms 48720 KB Output is correct
12 Correct 1468 ms 48732 KB Output is correct
13 Correct 405 ms 48720 KB Output is correct
14 Correct 2 ms 12888 KB Output is correct
15 Correct 695 ms 48768 KB Output is correct
16 Correct 54 ms 48732 KB Output is correct
17 Correct 44 ms 48732 KB Output is correct
18 Correct 2065 ms 48604 KB Output is correct
19 Correct 67 ms 48732 KB Output is correct
20 Correct 156 ms 48728 KB Output is correct
21 Correct 1375 ms 48984 KB Output is correct
22 Execution timed out 7023 ms 48720 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 12888 KB Output is correct
2 Execution timed out 7035 ms 276768 KB Time limit exceeded
3 Halted 0 ms 0 KB -