oj.uz

Submission #1042135

# Submission time Handle Problem Language Result Execution time Memory
1042135 2024-08-02T15:11:35 Z 0npata Dungeons Game (IOI21_dungeons) C++17
36 / 100
 3186 ms 1469288 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define vec vector

const int MXN = 50'050;
const int LOGN = 28;
const int LOGS = 28;

struct Data {
    int mnt;
    int sum;
    int32_t v;
};

Data binjmps[LOGS][MXN][LOGN];

int n;
vec<int32_t> s;
vec<int32_t> p;
vec<int32_t> w;
vec<int32_t> l;

const int MXS = 1e8+100;

void init(int32_t n_i, std::vector<int32_t> s_i, std::vector<int32_t> p_i, std::vector<int32_t> w_i, std::vector<int32_t> l_i) {
    // preprocessing fill in binjmps
    s =  s_i;
    s.push_back(0);
    p = p_i;
    w = w_i;
    w.push_back(n_i);
    l = l_i;
    n = n_i;

    for(int i = 0; i<LOGS; i++) {
        for(int j = 0; j<=n; j++) {
            if(s[j] > (1<<i)) {
                binjmps[i][j][0] = {s[j], p[j], l[j]};
            }
            else {
                binjmps[i][j][0] = {MXS, s[j], w[j]};
            }
        }
        for(int k = 1; k<LOGN; k++) {
            for(int j = 0; j<=n; j++) {
                auto nxt = &binjmps[i][binjmps[i][j][k-1].v][k-1];
                auto me = &binjmps[i][j][k-1];

                int nxt_mnt = (nxt->mnt == MXS) ? MXS : (nxt->mnt-min(me->sum, (int)nxt->mnt));
                binjmps[i][j][k] = {min(me->mnt, nxt_mnt), me->sum+nxt->sum, nxt->v};
            }
        }
    }

	return;
}

long long simulate(int32_t u, int32_t z) {
    
    int cur_s = z;
    for(int32_t i = 0; i<LOGS; i++) {
        //cerr << u << ' ' << cur_s << '\n';
        for(int32_t j = LOGN-1; j>=0; j--) {
            if(binjmps[i][u][j].mnt > cur_s) {
                cur_s += binjmps[i][u][j].sum;
                u = binjmps[i][u][j].v;
            }
        }
    }

    return cur_s;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 55644 KB Output is correct
2 Correct 4 ms 53592 KB Output is correct
3 Correct 15 ms 68444 KB Output is correct
4 Correct 595 ms 923364 KB Output is correct
5 Correct 14 ms 67164 KB Output is correct
6 Correct 543 ms 923408 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 57436 KB Output is correct
2 Runtime error 3186 ms 1469288 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 10 ms 57436 KB Output is correct
2 Correct 823 ms 924264 KB Output is correct
3 Correct 797 ms 924272 KB Output is correct
4 Correct 677 ms 924256 KB Output is correct
5 Correct 685 ms 924144 KB Output is correct
6 Correct 679 ms 924044 KB Output is correct
7 Correct 663 ms 924088 KB Output is correct
8 Correct 681 ms 924044 KB Output is correct
9 Correct 706 ms 924188 KB Output is correct
10 Correct 681 ms 924044 KB Output is correct
11 Correct 668 ms 924048 KB Output is correct
12 Correct 897 ms 924044 KB Output is correct
13 Correct 918 ms 924048 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 57436 KB Output is correct
2 Correct 823 ms 924264 KB Output is correct
3 Correct 797 ms 924272 KB Output is correct
4 Correct 677 ms 924256 KB Output is correct
5 Correct 685 ms 924144 KB Output is correct
6 Correct 679 ms 924044 KB Output is correct
7 Correct 663 ms 924088 KB Output is correct
8 Correct 681 ms 924044 KB Output is correct
9 Correct 706 ms 924188 KB Output is correct
10 Correct 681 ms 924044 KB Output is correct
11 Correct 668 ms 924048 KB Output is correct
12 Correct 897 ms 924044 KB Output is correct
13 Correct 918 ms 924048 KB Output is correct
14 Correct 10 ms 59228 KB Output is correct
15 Correct 710 ms 924144 KB Output is correct
16 Correct 840 ms 924304 KB Output is correct
17 Correct 707 ms 924052 KB Output is correct
18 Correct 720 ms 924092 KB Output is correct
19 Correct 689 ms 924140 KB Output is correct
20 Correct 689 ms 924136 KB Output is correct
21 Correct 712 ms 924048 KB Output is correct
22 Correct 712 ms 924300 KB Output is correct
23 Correct 711 ms 924044 KB Output is correct
24 Correct 823 ms 924048 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 57436 KB Output is correct
2 Correct 823 ms 924264 KB Output is correct
3 Correct 797 ms 924272 KB Output is correct
4 Correct 677 ms 924256 KB Output is correct
5 Correct 685 ms 924144 KB Output is correct
6 Correct 679 ms 924044 KB Output is correct
7 Correct 663 ms 924088 KB Output is correct
8 Correct 681 ms 924044 KB Output is correct
9 Correct 706 ms 924188 KB Output is correct
10 Correct 681 ms 924044 KB Output is correct
11 Correct 668 ms 924048 KB Output is correct
12 Correct 897 ms 924044 KB Output is correct
13 Correct 918 ms 924048 KB Output is correct
14 Correct 10 ms 59228 KB Output is correct
15 Correct 710 ms 924144 KB Output is correct
16 Correct 840 ms 924304 KB Output is correct
17 Correct 707 ms 924052 KB Output is correct
18 Correct 720 ms 924092 KB Output is correct
19 Correct 689 ms 924140 KB Output is correct
20 Correct 689 ms 924136 KB Output is correct
21 Correct 712 ms 924048 KB Output is correct
22 Correct 712 ms 924300 KB Output is correct
23 Correct 711 ms 924044 KB Output is correct
24 Correct 823 ms 924048 KB Output is correct
25 Correct 578 ms 923280 KB Output is correct
26 Incorrect 864 ms 924044 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 57436 KB Output is correct
2 Runtime error 3186 ms 1469288 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -