oj.uz

Submission #615479

# Submission time Handle Problem Language Result Execution time Memory
615479 2022-07-31T09:42:57 Z MadokaMagicaFan Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 455696 KB 
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
using vi = vector<int>;
using ai = array<ll, 2>;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second
/* #define ONPC */

const int K = 27;

vector<array<array<ll, 3>, 27>> j;
vector<array<ai, 27>> f;
vector<ll> d;

vi s, p, w, l;

int n;

void
init(int _n, vi _s, vi _p, vi _w, vi _l)
{
    n = _n;
    s = _s;
    p = _p;
    w = _w;
    l = _l;
    j.assign(n+1,{{}});
    f.assign(n+1,{{}});
    d.assign(n+1, 0);

    s.pb(0);
    p.pb(0);
    l.pb(n);
    w.pb(n);

    f[n][0] = {n,0};
    j[n][0] = {n,0,0};
    for (int i = n-1; i >= 0; --i) {
        d[i] = d[w[i]] + s[i];
        f[i][0] = {w[i], d[i]+s[i]};
        j[i][0] = {l[i], p[i], s[l[i]] - p[i]};
    }

    for (int k = 1; k < K; ++k) {
        for (int i = 0; i <= n; ++i) {
            f[i][k][0] = f[f[i][k-1][0]][k-1][0];
            f[i][k][1] = max(f[i][k-1][1], f[f[i][k-1][0]][k-1][1]);

            j[i][k][0] = j[j[i][k-1][0]][k-1][0];
            j[i][k][1] = j[i][k-1][1] + j[j[i][k-1][0]][k-1][1];
            j[i][k][2] = min(j[i][k-1][2], j[j[i][k-1][0]][k-1][2]-j[i][k-1][1]);
        }
    }

    return;
}

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

    while (x < n) {
        /* cout << x << ' ' << z << ' ' << s[x] << endl; */
        if (z >= s[x]) {
            for (int k = K-1; k >= 0; --k) {
                if (z + d[x] >= f[x][k][1]) {
                    z += d[x];
                    x = f[x][k][0];
                    z -= d[x];
                }
            }
            /* z += s[x]; */
            /* x = w[x]; */
        } else {
            for (int k = K-1; k >= 0; --k) {
                if (z < j[x][k][2])
                {
                    z += j[x][k][1];
                    x = j[x][k][0];
                }
            }

            z += p[x];
            x = l[x];
        }
    }

    assert(x == n);
    return z;
}


#ifdef ONPC
void
solve()
{
    int n, q;
    cin >> n >> q;
    vector<int> s(n), p(n), w(n) ,l(n);
    for (int i = 0; i < n; ++i) cin >> s[i];
    for (int i = 0; i < n; ++i) cin >> p[i];
    for (int i = 0; i < n; ++i) cin >> w[i];
    for (int i = 0; i < n; ++i) cin >> l[i];

    init(n,s,p,w,l);

    int z, x;
    while (q--) {
        cin >> x >> z;
        cout << simulate(x,z) << endl;
    }
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 2516 KB Output is correct
4 Correct 94 ms 57120 KB Output is correct
5 Correct 3 ms 2484 KB Output is correct
6 Correct 75 ms 56968 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1516 KB Output is correct
2 Correct 716 ms 454184 KB Output is correct
3 Correct 732 ms 454284 KB Output is correct
4 Correct 770 ms 455696 KB Output is correct
5 Correct 691 ms 455696 KB Output is correct
6 Correct 733 ms 454176 KB Output is correct
7 Correct 671 ms 452380 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 142 ms 58360 KB Output is correct
3 Correct 127 ms 58428 KB Output is correct
4 Correct 109 ms 57948 KB Output is correct
5 Correct 125 ms 57848 KB Output is correct
6 Correct 107 ms 58120 KB Output is correct
7 Correct 107 ms 58124 KB Output is correct
8 Correct 108 ms 57860 KB Output is correct
9 Correct 107 ms 57852 KB Output is correct
10 Correct 103 ms 57736 KB Output is correct
11 Correct 136 ms 58108 KB Output is correct
12 Correct 202 ms 58108 KB Output is correct
13 Correct 183 ms 58068 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 142 ms 58360 KB Output is correct
3 Correct 127 ms 58428 KB Output is correct
4 Correct 109 ms 57948 KB Output is correct
5 Correct 125 ms 57848 KB Output is correct
6 Correct 107 ms 58120 KB Output is correct
7 Correct 107 ms 58124 KB Output is correct
8 Correct 108 ms 57860 KB Output is correct
9 Correct 107 ms 57852 KB Output is correct
10 Correct 103 ms 57736 KB Output is correct
11 Correct 136 ms 58108 KB Output is correct
12 Correct 202 ms 58108 KB Output is correct
13 Correct 183 ms 58068 KB Output is correct
14 Correct 3 ms 1492 KB Output is correct
15 Correct 313 ms 58224 KB Output is correct
16 Correct 120 ms 58376 KB Output is correct
17 Correct 132 ms 57852 KB Output is correct
18 Correct 126 ms 57980 KB Output is correct
19 Correct 131 ms 58216 KB Output is correct
20 Correct 139 ms 57848 KB Output is correct
21 Correct 111 ms 57976 KB Output is correct
22 Execution timed out 7047 ms 57952 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 1492 KB Output is correct
2 Correct 142 ms 58360 KB Output is correct
3 Correct 127 ms 58428 KB Output is correct
4 Correct 109 ms 57948 KB Output is correct
5 Correct 125 ms 57848 KB Output is correct
6 Correct 107 ms 58120 KB Output is correct
7 Correct 107 ms 58124 KB Output is correct
8 Correct 108 ms 57860 KB Output is correct
9 Correct 107 ms 57852 KB Output is correct
10 Correct 103 ms 57736 KB Output is correct
11 Correct 136 ms 58108 KB Output is correct
12 Correct 202 ms 58108 KB Output is correct
13 Correct 183 ms 58068 KB Output is correct
14 Correct 3 ms 1492 KB Output is correct
15 Correct 313 ms 58224 KB Output is correct
16 Correct 120 ms 58376 KB Output is correct
17 Correct 132 ms 57852 KB Output is correct
18 Correct 126 ms 57980 KB Output is correct
19 Correct 131 ms 58216 KB Output is correct
20 Correct 139 ms 57848 KB Output is correct
21 Correct 111 ms 57976 KB Output is correct
22 Execution timed out 7047 ms 57952 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 1516 KB Output is correct
2 Correct 716 ms 454184 KB Output is correct
3 Correct 732 ms 454284 KB Output is correct
4 Correct 770 ms 455696 KB Output is correct
5 Correct 691 ms 455696 KB Output is correct
6 Correct 733 ms 454176 KB Output is correct
7 Correct 671 ms 452380 KB Output is correct
8 Correct 2 ms 1492 KB Output is correct
9 Correct 142 ms 58360 KB Output is correct
10 Correct 127 ms 58428 KB Output is correct
11 Correct 109 ms 57948 KB Output is correct
12 Correct 125 ms 57848 KB Output is correct
13 Correct 107 ms 58120 KB Output is correct
14 Correct 107 ms 58124 KB Output is correct
15 Correct 108 ms 57860 KB Output is correct
16 Correct 107 ms 57852 KB Output is correct
17 Correct 103 ms 57736 KB Output is correct
18 Correct 136 ms 58108 KB Output is correct
19 Correct 202 ms 58108 KB Output is correct
20 Correct 183 ms 58068 KB Output is correct
21 Correct 3 ms 1492 KB Output is correct
22 Correct 313 ms 58224 KB Output is correct
23 Correct 120 ms 58376 KB Output is correct
24 Correct 132 ms 57852 KB Output is correct
25 Correct 126 ms 57980 KB Output is correct
26 Correct 131 ms 58216 KB Output is correct
27 Correct 139 ms 57848 KB Output is correct
28 Correct 111 ms 57976 KB Output is correct
29 Execution timed out 7047 ms 57952 KB Time limit exceeded
30 Halted 0 ms 0 KB -