oj.uz

Submission #898978

# Submission time Handle Problem Language Result Execution time Memory
898978 2024-01-05T10:27:20 Z Trisanu_Das Dungeons Game (IOI21_dungeons) C++17
63 / 100
 1650 ms 1083380 KB 
#include<bits/stdc++.h>
#include "dungeons.h"
using namespace std;

const int MAX_N = 50009;
int msh[MAX_N][26][26];
long long a, b, c, d, e, i, j, k, ii, jj, zx, xc, S[MAX_N], P[MAX_N], W[MAX_N], L[MAX_N], dis[MAX_N][26][26], mn[MAX_N][26][26], z;

void init(int Nn, vector<int> Ss, vector<int> Pp, vector<int> Ww, vector<int> Ll) {
    a = Nn;
    for (i = 0; i < a; i++) {
        S[i + 1] = Ss[i];
        P[i + 1] = Pp[i];
        W[i + 1] = Ww[i] + 1;
        L[i + 1] = Ll[i] + 1;
    }
    for (i = 1; i <= a; i++) {
        for (k = 0; k <= 24; k++) {
            if (S[i] < (1 << k)) {
                msh[i][0][k] = W[i];
                dis[i][0][k] = S[i];
                mn[i][0][k] = LLONG_MAX;
            } else {
                msh[i][0][k] = L[i];
                dis[i][0][k] = P[i];
                mn[i][0][k] = S[i];
            }
        }
    }

    for (j = 1; j <= 24; j++) {
        for (i = 1; i <= a; i++) {
            for (k = 0; k <= 24; k++) {
                msh[i][j][k] = msh[msh[i][j - 1][k]][j - 1][k];
                dis[i][j][k] = dis[i][j - 1][k] + dis[msh[i][j - 1][k]][j - 1][k];
                mn[i][j][k] = min(mn[i][j - 1][k], mn[msh[i][j - 1][k]][j - 1][k] - dis[i][j - 1][k]);
            }
        }
    }
}

long long simulate(int Xx, int Zz) {
    c = Xx + 1;
    z = Zz;
    while (c != a + 1) {
        for (k = 24; k >= 0; k--) if (z >= (1 << k)) break;
        for (j = 24; j >= 0; j--) {
            if (msh[c][j][k] == 0) continue;
            if (mn[c][j][k] > z) {
                z += dis[c][j][k];
                c = msh[c][j][k];
            }
        }
        if (c == a + 1) break;
        if (z >= S[c]) {
            z += S[c];
            c = W[c];
        } else {
            z += P[c];
            c = L[c];
        }
    }
    return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 11 ms 37652 KB Output is correct
4 Correct 713 ms 665792 KB Output is correct
5 Correct 12 ms 37464 KB Output is correct
6 Correct 806 ms 665904 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21084 KB Output is correct
2 Runtime error 708 ms 1083380 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 5 ms 21096 KB Output is correct
2 Correct 642 ms 666796 KB Output is correct
3 Correct 604 ms 667344 KB Output is correct
4 Correct 575 ms 666676 KB Output is correct
5 Correct 596 ms 666724 KB Output is correct
6 Correct 566 ms 666676 KB Output is correct
7 Correct 600 ms 666964 KB Output is correct
8 Correct 555 ms 666900 KB Output is correct
9 Correct 560 ms 666904 KB Output is correct
10 Correct 606 ms 666548 KB Output is correct
11 Correct 688 ms 667160 KB Output is correct
12 Correct 860 ms 667168 KB Output is correct
13 Correct 697 ms 667164 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21096 KB Output is correct
2 Correct 642 ms 666796 KB Output is correct
3 Correct 604 ms 667344 KB Output is correct
4 Correct 575 ms 666676 KB Output is correct
5 Correct 596 ms 666724 KB Output is correct
6 Correct 566 ms 666676 KB Output is correct
7 Correct 600 ms 666964 KB Output is correct
8 Correct 555 ms 666900 KB Output is correct
9 Correct 560 ms 666904 KB Output is correct
10 Correct 606 ms 666548 KB Output is correct
11 Correct 688 ms 667160 KB Output is correct
12 Correct 860 ms 667168 KB Output is correct
13 Correct 697 ms 667164 KB Output is correct
14 Correct 6 ms 21084 KB Output is correct
15 Correct 607 ms 667460 KB Output is correct
16 Correct 617 ms 667528 KB Output is correct
17 Correct 623 ms 666904 KB Output is correct
18 Correct 643 ms 667060 KB Output is correct
19 Correct 602 ms 667156 KB Output is correct
20 Correct 645 ms 666952 KB Output is correct
21 Correct 616 ms 667036 KB Output is correct
22 Correct 562 ms 667036 KB Output is correct
23 Correct 758 ms 667164 KB Output is correct
24 Correct 826 ms 667164 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21096 KB Output is correct
2 Correct 642 ms 666796 KB Output is correct
3 Correct 604 ms 667344 KB Output is correct
4 Correct 575 ms 666676 KB Output is correct
5 Correct 596 ms 666724 KB Output is correct
6 Correct 566 ms 666676 KB Output is correct
7 Correct 600 ms 666964 KB Output is correct
8 Correct 555 ms 666900 KB Output is correct
9 Correct 560 ms 666904 KB Output is correct
10 Correct 606 ms 666548 KB Output is correct
11 Correct 688 ms 667160 KB Output is correct
12 Correct 860 ms 667168 KB Output is correct
13 Correct 697 ms 667164 KB Output is correct
14 Correct 6 ms 21084 KB Output is correct
15 Correct 607 ms 667460 KB Output is correct
16 Correct 617 ms 667528 KB Output is correct
17 Correct 623 ms 666904 KB Output is correct
18 Correct 643 ms 667060 KB Output is correct
19 Correct 602 ms 667156 KB Output is correct
20 Correct 645 ms 666952 KB Output is correct
21 Correct 616 ms 667036 KB Output is correct
22 Correct 562 ms 667036 KB Output is correct
23 Correct 758 ms 667164 KB Output is correct
24 Correct 826 ms 667164 KB Output is correct
25 Correct 569 ms 666616 KB Output is correct
26 Correct 641 ms 667508 KB Output is correct
27 Correct 592 ms 666852 KB Output is correct
28 Correct 520 ms 666964 KB Output is correct
29 Correct 639 ms 667420 KB Output is correct
30 Correct 804 ms 667448 KB Output is correct
31 Correct 706 ms 666940 KB Output is correct
32 Correct 825 ms 667096 KB Output is correct
33 Correct 927 ms 666960 KB Output is correct
34 Correct 1650 ms 666964 KB Output is correct
35 Correct 695 ms 667008 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21084 KB Output is correct
2 Runtime error 708 ms 1083380 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -