oj.uz

Submission #623715

# Submission time Handle Problem Language Result Execution time Memory
623715 2022-08-06T11:32:19 Z MohamedFaresNebili Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3910 ms 1537312 KB 
#include <bits/stdc++.h>

            using namespace std;
            using ll = long long;

            ll N, A[8][400005][20], B[8][400005][20], C[8][400005][20];
            ll S[400005], P[400005], W[400005], L[400005];

            void init(int n, vector<int> s, vector<int> p,
                      vector<int> w, vector<int> l) {
                N = n;
                for(int i = 0; i < N; i++)
                    S[i] = s[i], P[i] = p[i], W[i] = w[i], L[i] = l[i];
                for(int l = 0; l < 8; l++)
                    for(int i = 0; i < 20; i++)
                        A[l][N][i] = N, B[l][N][i] = 0, C[l][N][i] = 1e9;
                ll cur = 1;
                for(int l = 0; l < 8; l++) {
                    for(int i = 0; i < N; i++) {
                        if(S[i] <= cur) A[l][i][0] = W[i], B[l][i][0] = S[i], C[l][i][0] = 1e9;
                        else A[l][i][0] = L[i], B[l][i][0] = P[i], C[l][i][0] = S[i];
                    }
                    for(int j = 1; j < 20; j++) {
                        for(int i = 0; i < N; i++) {
                            A[l][i][j] = A[l][A[l][i][j - 1]][j - 1];
                            B[l][i][j] = B[l][i][j - 1] + B[l][A[l][i][j - 1]][j - 1];
                            C[l][i][j] = C[l][i][j - 1];
                            if(C[l][A[l][i][j - 1]][j - 1] != 1e9)
                                C[l][i][j] = min(C[l][i][j], max(C[l][A[l][i][j - 1]][j - 1] - B[l][i][j - 1], 0ll));
                        }
                    }
                    cur *= 10;
                }
            }

            long long simulate(int x, int t) {
                ll cur = 1, lvl = 0, z = t;
                while(x != N) {
                    while(lvl < 7 && cur * 10 <= z) lvl++, cur *= 10;
                    for(int l = 18; l >= 0; l--) {
                        if(A[lvl][x][l] != N && min((ll)1e7, z) < C[lvl][x][l])
                            z += B[lvl][x][l], x = A[lvl][x][l];
                    }
                    if(z < S[x]) z += P[x], x = L[x];
                    else z += S[x], x = W[x];
                }
                return z;
            }

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Correct 6 ms 8128 KB Output is correct
4 Correct 321 ms 192440 KB Output is correct
5 Correct 7 ms 8148 KB Output is correct
6 Correct 286 ms 192320 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4308 KB Output is correct
2 Correct 2624 ms 1529840 KB Output is correct
3 Correct 2495 ms 1529752 KB Output is correct
4 Correct 2762 ms 1529480 KB Output is correct
5 Correct 2561 ms 1529460 KB Output is correct
6 Correct 2699 ms 1529016 KB Output is correct
7 Correct 2487 ms 1529112 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 340 ms 192356 KB Output is correct
3 Correct 356 ms 192204 KB Output is correct
4 Correct 335 ms 192272 KB Output is correct
5 Correct 332 ms 192284 KB Output is correct
6 Correct 367 ms 192200 KB Output is correct
7 Correct 384 ms 192212 KB Output is correct
8 Correct 366 ms 192336 KB Output is correct
9 Correct 308 ms 192228 KB Output is correct
10 Correct 373 ms 192204 KB Output is correct
11 Correct 389 ms 192436 KB Output is correct
12 Correct 2286 ms 192200 KB Output is correct
13 Correct 2082 ms 192256 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 340 ms 192356 KB Output is correct
3 Correct 356 ms 192204 KB Output is correct
4 Correct 335 ms 192272 KB Output is correct
5 Correct 332 ms 192284 KB Output is correct
6 Correct 367 ms 192200 KB Output is correct
7 Correct 384 ms 192212 KB Output is correct
8 Correct 366 ms 192336 KB Output is correct
9 Correct 308 ms 192228 KB Output is correct
10 Correct 373 ms 192204 KB Output is correct
11 Correct 389 ms 192436 KB Output is correct
12 Correct 2286 ms 192200 KB Output is correct
13 Correct 2082 ms 192256 KB Output is correct
14 Correct 3 ms 4308 KB Output is correct
15 Correct 320 ms 192192 KB Output is correct
16 Correct 344 ms 192288 KB Output is correct
17 Correct 325 ms 192204 KB Output is correct
18 Correct 328 ms 192292 KB Output is correct
19 Correct 347 ms 192312 KB Output is correct
20 Correct 335 ms 192204 KB Output is correct
21 Correct 335 ms 192308 KB Output is correct
22 Correct 374 ms 192324 KB Output is correct
23 Correct 369 ms 192200 KB Output is correct
24 Correct 570 ms 192204 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 340 ms 192356 KB Output is correct
3 Correct 356 ms 192204 KB Output is correct
4 Correct 335 ms 192272 KB Output is correct
5 Correct 332 ms 192284 KB Output is correct
6 Correct 367 ms 192200 KB Output is correct
7 Correct 384 ms 192212 KB Output is correct
8 Correct 366 ms 192336 KB Output is correct
9 Correct 308 ms 192228 KB Output is correct
10 Correct 373 ms 192204 KB Output is correct
11 Correct 389 ms 192436 KB Output is correct
12 Correct 2286 ms 192200 KB Output is correct
13 Correct 2082 ms 192256 KB Output is correct
14 Correct 3 ms 4308 KB Output is correct
15 Correct 320 ms 192192 KB Output is correct
16 Correct 344 ms 192288 KB Output is correct
17 Correct 325 ms 192204 KB Output is correct
18 Correct 328 ms 192292 KB Output is correct
19 Correct 347 ms 192312 KB Output is correct
20 Correct 335 ms 192204 KB Output is correct
21 Correct 335 ms 192308 KB Output is correct
22 Correct 374 ms 192324 KB Output is correct
23 Correct 369 ms 192200 KB Output is correct
24 Correct 570 ms 192204 KB Output is correct
25 Correct 372 ms 191528 KB Output is correct
26 Correct 415 ms 192272 KB Output is correct
27 Correct 311 ms 192256 KB Output is correct
28 Correct 306 ms 192276 KB Output is correct
29 Correct 334 ms 192284 KB Output is correct
30 Correct 340 ms 192348 KB Output is correct
31 Correct 340 ms 192204 KB Output is correct
32 Correct 411 ms 192312 KB Output is correct
33 Correct 613 ms 193480 KB Output is correct
34 Correct 996 ms 193368 KB Output is correct
35 Correct 479 ms 193400 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4308 KB Output is correct
2 Correct 2624 ms 1529840 KB Output is correct
3 Correct 2495 ms 1529752 KB Output is correct
4 Correct 2762 ms 1529480 KB Output is correct
5 Correct 2561 ms 1529460 KB Output is correct
6 Correct 2699 ms 1529016 KB Output is correct
7 Correct 2487 ms 1529112 KB Output is correct
8 Correct 3 ms 4308 KB Output is correct
9 Correct 340 ms 192356 KB Output is correct
10 Correct 356 ms 192204 KB Output is correct
11 Correct 335 ms 192272 KB Output is correct
12 Correct 332 ms 192284 KB Output is correct
13 Correct 367 ms 192200 KB Output is correct
14 Correct 384 ms 192212 KB Output is correct
15 Correct 366 ms 192336 KB Output is correct
16 Correct 308 ms 192228 KB Output is correct
17 Correct 373 ms 192204 KB Output is correct
18 Correct 389 ms 192436 KB Output is correct
19 Correct 2286 ms 192200 KB Output is correct
20 Correct 2082 ms 192256 KB Output is correct
21 Correct 3 ms 4308 KB Output is correct
22 Correct 320 ms 192192 KB Output is correct
23 Correct 344 ms 192288 KB Output is correct
24 Correct 325 ms 192204 KB Output is correct
25 Correct 328 ms 192292 KB Output is correct
26 Correct 347 ms 192312 KB Output is correct
27 Correct 335 ms 192204 KB Output is correct
28 Correct 335 ms 192308 KB Output is correct
29 Correct 374 ms 192324 KB Output is correct
30 Correct 369 ms 192200 KB Output is correct
31 Correct 570 ms 192204 KB Output is correct
32 Correct 372 ms 191528 KB Output is correct
33 Correct 415 ms 192272 KB Output is correct
34 Correct 311 ms 192256 KB Output is correct
35 Correct 306 ms 192276 KB Output is correct
36 Correct 334 ms 192284 KB Output is correct
37 Correct 340 ms 192348 KB Output is correct
38 Correct 340 ms 192204 KB Output is correct
39 Correct 411 ms 192312 KB Output is correct
40 Correct 613 ms 193480 KB Output is correct
41 Correct 996 ms 193368 KB Output is correct
42 Correct 479 ms 193400 KB Output is correct
43 Correct 0 ms 468 KB Output is correct
44 Correct 3 ms 4384 KB Output is correct
45 Correct 3095 ms 1537040 KB Output is correct
46 Correct 2673 ms 1534220 KB Output is correct
47 Correct 2516 ms 1534256 KB Output is correct
48 Correct 2445 ms 1535940 KB Output is correct
49 Correct 2876 ms 1536648 KB Output is correct
50 Correct 2652 ms 1535284 KB Output is correct
51 Correct 2417 ms 1535336 KB Output is correct
52 Correct 2867 ms 1533000 KB Output is correct
53 Correct 3436 ms 1532908 KB Output is correct
54 Correct 3077 ms 1533420 KB Output is correct
55 Correct 3699 ms 1533556 KB Output is correct
56 Correct 3142 ms 1533520 KB Output is correct
57 Correct 3325 ms 1533572 KB Output is correct
58 Correct 3837 ms 1533672 KB Output is correct
59 Correct 3739 ms 1533760 KB Output is correct
60 Correct 3910 ms 1533848 KB Output is correct
61 Correct 3661 ms 1537312 KB Output is correct