oj.uz

Submission #1042143

# Submission time Handle Problem Language Result Execution time Memory
1042143 2024-08-02T15:20:19 Z 0npata Dungeons Game (IOI21_dungeons) C++17
36 / 100
 3782 ms 1607852 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 = 30;
const int LOGS = 30;

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};
                assert(binjmps[i][j][k].sum >= 0);
            }
        }
    }

	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;
            }
        }
    }

cerr << cur_s << '\n';
    return cur_s;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 51544 KB Output is correct
2 Correct 4 ms 49756 KB Output is correct
3 Correct 16 ms 70476 KB Output is correct
4 Correct 622 ms 1060752 KB Output is correct
5 Correct 16 ms 74584 KB Output is correct
6 Correct 606 ms 1060624 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 62056 KB Output is correct
2 Runtime error 3782 ms 1607852 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 14 ms 62052 KB Output is correct
2 Correct 976 ms 1060480 KB Output is correct
3 Correct 998 ms 1060732 KB Output is correct
4 Correct 861 ms 1060492 KB Output is correct
5 Correct 891 ms 1060672 KB Output is correct
6 Correct 858 ms 1061472 KB Output is correct
7 Correct 815 ms 1061536 KB Output is correct
8 Correct 829 ms 1061396 KB Output is correct
9 Correct 859 ms 1061264 KB Output is correct
10 Correct 809 ms 1060980 KB Output is correct
11 Correct 853 ms 1061212 KB Output is correct
12 Correct 1029 ms 1061712 KB Output is correct
13 Correct 1043 ms 1061472 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 62052 KB Output is correct
2 Correct 976 ms 1060480 KB Output is correct
3 Correct 998 ms 1060732 KB Output is correct
4 Correct 861 ms 1060492 KB Output is correct
5 Correct 891 ms 1060672 KB Output is correct
6 Correct 858 ms 1061472 KB Output is correct
7 Correct 815 ms 1061536 KB Output is correct
8 Correct 829 ms 1061396 KB Output is correct
9 Correct 859 ms 1061264 KB Output is correct
10 Correct 809 ms 1060980 KB Output is correct
11 Correct 853 ms 1061212 KB Output is correct
12 Correct 1029 ms 1061712 KB Output is correct
13 Correct 1043 ms 1061472 KB Output is correct
14 Correct 15 ms 67160 KB Output is correct
15 Correct 875 ms 1061760 KB Output is correct
16 Correct 1020 ms 1061760 KB Output is correct
17 Correct 866 ms 1061440 KB Output is correct
18 Correct 877 ms 1061516 KB Output is correct
19 Correct 839 ms 1061508 KB Output is correct
20 Correct 847 ms 1061504 KB Output is correct
21 Correct 866 ms 1061532 KB Output is correct
22 Correct 846 ms 1061268 KB Output is correct
23 Correct 833 ms 1061248 KB Output is correct
24 Correct 978 ms 1061588 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 62052 KB Output is correct
2 Correct 976 ms 1060480 KB Output is correct
3 Correct 998 ms 1060732 KB Output is correct
4 Correct 861 ms 1060492 KB Output is correct
5 Correct 891 ms 1060672 KB Output is correct
6 Correct 858 ms 1061472 KB Output is correct
7 Correct 815 ms 1061536 KB Output is correct
8 Correct 829 ms 1061396 KB Output is correct
9 Correct 859 ms 1061264 KB Output is correct
10 Correct 809 ms 1060980 KB Output is correct
11 Correct 853 ms 1061212 KB Output is correct
12 Correct 1029 ms 1061712 KB Output is correct
13 Correct 1043 ms 1061472 KB Output is correct
14 Correct 15 ms 67160 KB Output is correct
15 Correct 875 ms 1061760 KB Output is correct
16 Correct 1020 ms 1061760 KB Output is correct
17 Correct 866 ms 1061440 KB Output is correct
18 Correct 877 ms 1061516 KB Output is correct
19 Correct 839 ms 1061508 KB Output is correct
20 Correct 847 ms 1061504 KB Output is correct
21 Correct 866 ms 1061532 KB Output is correct
22 Correct 846 ms 1061268 KB Output is correct
23 Correct 833 ms 1061248 KB Output is correct
24 Correct 978 ms 1061588 KB Output is correct
25 Correct 642 ms 1060492 KB Output is correct
26 Incorrect 996 ms 1061812 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 12 ms 62056 KB Output is correct
2 Runtime error 3782 ms 1607852 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -