oj.uz

Submission #592399

# Submission time Handle Problem Language Result Execution time Memory
592399 2022-07-09T06:56:52 Z grt Dungeons Game (IOI21_dungeons) C++17
63 / 100
 2737 ms 741292 KB 
//GRT_2018
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 50 * 1000 + 10, LOG = 25;
const ll INF = 1e18;
int n;
pair<int, ll>jp[nax][LOG][LOG];
ll lim[nax][LOG][LOG];
vi s, p, w, l;


void init(int N, vi _s, vi _p, vi _w, vi _l) {
        n = N;
        s = _s, w = _w, p = _p, l = _l;
        s.PB(n);
        for(int j = 0; j < LOG; ++j) {
            for(int i = 0; i < n; ++i) {
                        int num = (1 << j);
                        if(num >= s[i]) {
                            jp[i][j][0] = {w[i], s[i]};
                                lim[i][j][0] = INF;
                        } else {
                                jp[i][j][0] = {l[i], p[i]};
                                lim[i][j][0] = s[i];
                        }
        }
                jp[n][j][0] = {n, 0};
                lim[n][j][0] = INF;
        }
        for(int k = 1; k < LOG; ++k) {
                for(int j = LOG - 1; j >= 0; --j) {
                        for(int i = 0; i < n; ++i) {
                                auto [id, sum] = jp[i][j][k - 1];
                                lim[i][j][k] = min(lim[i][j][k - 1], lim[id][j][k - 1] - sum);
                                jp[i][j][k] = {jp[id][j][k - 1].ST, sum + jp[id][j][k - 1].ND};
                        }
                        jp[n][j][k] = {n, 0};
                        lim[n][j][k] = INF;
                }
        }
}

ll simulate(int x, int zz) {
        int inf = 10'000'000;
        ll z = zz;
        while(x != n) {
                int bit = LOG - 1;
                if(z < inf) {
                        bit = 31 - __builtin_clz(z);
                }
                for(int i = LOG - 1; i >= 0; --i) {
                        if(z < lim[x][bit][i]) {
                                z += jp[x][bit][i].ND;
                                x = jp[x][bit][i].ST;
                        }
                }
//              cerr << x << " " << z << "\n";
                if(x == n) {
                        return z;
                }
                if(z >= s[x]) {
                        z += s[x];
                        x = w[x];
                } else {
                        z += p[x];
                        x = l[x];
                }
        }
        return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 46 ms 29808 KB Output is correct
4 Correct 1444 ms 737032 KB Output is correct
5 Correct 44 ms 29900 KB Output is correct
6 Correct 1427 ms 737028 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15060 KB Output is correct
2 Runtime error 779 ms 741292 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 17 ms 15060 KB Output is correct
2 Correct 1605 ms 737568 KB Output is correct
3 Correct 1462 ms 737580 KB Output is correct
4 Correct 1374 ms 737576 KB Output is correct
5 Correct 1357 ms 737568 KB Output is correct
6 Correct 1502 ms 737632 KB Output is correct
7 Correct 1533 ms 737564 KB Output is correct
8 Correct 1374 ms 737532 KB Output is correct
9 Correct 1458 ms 737324 KB Output is correct
10 Correct 1435 ms 737568 KB Output is correct
11 Correct 1678 ms 737576 KB Output is correct
12 Correct 2069 ms 737576 KB Output is correct
13 Correct 1727 ms 738568 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15060 KB Output is correct
2 Correct 1605 ms 737568 KB Output is correct
3 Correct 1462 ms 737580 KB Output is correct
4 Correct 1374 ms 737576 KB Output is correct
5 Correct 1357 ms 737568 KB Output is correct
6 Correct 1502 ms 737632 KB Output is correct
7 Correct 1533 ms 737564 KB Output is correct
8 Correct 1374 ms 737532 KB Output is correct
9 Correct 1458 ms 737324 KB Output is correct
10 Correct 1435 ms 737568 KB Output is correct
11 Correct 1678 ms 737576 KB Output is correct
12 Correct 2069 ms 737576 KB Output is correct
13 Correct 1727 ms 738568 KB Output is correct
14 Correct 17 ms 15096 KB Output is correct
15 Correct 1471 ms 738700 KB Output is correct
16 Correct 1554 ms 738940 KB Output is correct
17 Correct 1443 ms 738420 KB Output is correct
18 Correct 1495 ms 738440 KB Output is correct
19 Correct 1642 ms 738572 KB Output is correct
20 Correct 1576 ms 738312 KB Output is correct
21 Correct 1589 ms 738448 KB Output is correct
22 Correct 1542 ms 738604 KB Output is correct
23 Correct 1849 ms 738568 KB Output is correct
24 Correct 2531 ms 738576 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15060 KB Output is correct
2 Correct 1605 ms 737568 KB Output is correct
3 Correct 1462 ms 737580 KB Output is correct
4 Correct 1374 ms 737576 KB Output is correct
5 Correct 1357 ms 737568 KB Output is correct
6 Correct 1502 ms 737632 KB Output is correct
7 Correct 1533 ms 737564 KB Output is correct
8 Correct 1374 ms 737532 KB Output is correct
9 Correct 1458 ms 737324 KB Output is correct
10 Correct 1435 ms 737568 KB Output is correct
11 Correct 1678 ms 737576 KB Output is correct
12 Correct 2069 ms 737576 KB Output is correct
13 Correct 1727 ms 738568 KB Output is correct
14 Correct 17 ms 15096 KB Output is correct
15 Correct 1471 ms 738700 KB Output is correct
16 Correct 1554 ms 738940 KB Output is correct
17 Correct 1443 ms 738420 KB Output is correct
18 Correct 1495 ms 738440 KB Output is correct
19 Correct 1642 ms 738572 KB Output is correct
20 Correct 1576 ms 738312 KB Output is correct
21 Correct 1589 ms 738448 KB Output is correct
22 Correct 1542 ms 738604 KB Output is correct
23 Correct 1849 ms 738568 KB Output is correct
24 Correct 2531 ms 738576 KB Output is correct
25 Correct 1805 ms 737892 KB Output is correct
26 Correct 1868 ms 738940 KB Output is correct
27 Correct 1657 ms 738312 KB Output is correct
28 Correct 1733 ms 738424 KB Output is correct
29 Correct 1850 ms 738824 KB Output is correct
30 Correct 2060 ms 738572 KB Output is correct
31 Correct 1863 ms 738320 KB Output is correct
32 Correct 2280 ms 738444 KB Output is correct
33 Correct 2577 ms 738272 KB Output is correct
34 Correct 2737 ms 738140 KB Output is correct
35 Correct 1920 ms 738440 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15060 KB Output is correct
2 Runtime error 779 ms 741292 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -