oj.uz

Submission #523417

# Submission time Handle Problem Language Result Execution time Memory
523417 2022-02-07T15:42:24 Z eecs Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3809 ms 1675384 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int B = 16, L = 7, INF = 0x3f3f3f3f;
const int maxn = 400005;
int n, lim[L], s[maxn], p[maxn], w[maxn], l[maxn];

struct node {
    int to; ll sum; int req;
    node operator + (const node b) const {
        return (node){b.to, sum + b.sum, b.req == INF ? req : max(0LL, min((ll)req, b.req - sum))};
    }
} f[L][25][maxn];

void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
    n = _n, w[n] = 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];
    }
    auto init = [&](int X, node g[][maxn]) {
        for (int i = 0; i < n; i++) {
            g[0][i] = X >= s[i] ? node{w[i], s[i], INF} : node{l[i], p[i], s[i]};
        }
        for (int k = 1; k < 25; k++) {
            for (int i = 0; i < n; i++) {
                g[k][i] = g[k - 1][i] + g[k - 1][g[k - 1][i].to];
            }
        }
    };
    for (int d = 0; d < L; d++) {
        init(lim[d] = !d ? 1 : lim[d - 1] * B, f[d]);
    }
}

ll simulate(int x, int _z) {
    ll z = _z;
    int i = 0;
    while (x < n) {
        while (i + 1 < L && z >= lim[i + 1]) i++;
        for (int j = 24; ~j; j--) {
            if (f[i][j][x].to == n || f[i][j][x].req != INF && f[i][j][x].req <= z) continue;
            z += f[i][j][x].sum, x = f[i][j][x].to;
        }
        if (z >= s[x]) z += s[x], x = w[x];
        else z += p[x], x = l[x];
    }
    return z;
}

Compilation message

dungeons.cpp: In member function 'node node::operator+(node) const':
dungeons.cpp:13:55: warning: narrowing conversion of '((((int)b.node::req) == ((int)INF)) ? ((long long int)((int)((const node*)this)->node::req)) : ((long long int)std::max<long long int>(0, (* & std::min<long long int>(((ll)((int)((const node*)this)->node::req)), (((long long int)((int)b.node::req)) - ((long long int)((const node*)this)->node::sum)))))))' from 'long long int' to 'int' [-Wnarrowing]
   13 |         return (node){b.to, sum + b.sum, b.req == INF ? req : max(0LL, min((ll)req, b.req - sum))};
      |                                          ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dungeons.cpp: In function 'll simulate(int, int)':
dungeons.cpp:43:61: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   43 |             if (f[i][j][x].to == n || f[i][j][x].req != INF && f[i][j][x].req <= z) continue;
      |                                       ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1740 KB Output is correct
3 Correct 6 ms 10032 KB Output is correct
4 Correct 117 ms 210600 KB Output is correct
5 Correct 8 ms 10060 KB Output is correct
6 Correct 135 ms 210340 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5836 KB Output is correct
2 Correct 1259 ms 1670508 KB Output is correct
3 Correct 1079 ms 1670704 KB Output is correct
4 Correct 1027 ms 1672228 KB Output is correct
5 Correct 1153 ms 1672172 KB Output is correct
6 Correct 1071 ms 1670552 KB Output is correct
7 Correct 1074 ms 1668836 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5836 KB Output is correct
2 Correct 264 ms 212020 KB Output is correct
3 Correct 217 ms 212144 KB Output is correct
4 Correct 160 ms 211464 KB Output is correct
5 Correct 170 ms 211496 KB Output is correct
6 Correct 243 ms 211624 KB Output is correct
7 Correct 216 ms 211516 KB Output is correct
8 Correct 176 ms 211268 KB Output is correct
9 Correct 172 ms 211264 KB Output is correct
10 Correct 197 ms 211136 KB Output is correct
11 Correct 218 ms 211528 KB Output is correct
12 Correct 272 ms 211756 KB Output is correct
13 Correct 205 ms 211528 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5836 KB Output is correct
2 Correct 264 ms 212020 KB Output is correct
3 Correct 217 ms 212144 KB Output is correct
4 Correct 160 ms 211464 KB Output is correct
5 Correct 170 ms 211496 KB Output is correct
6 Correct 243 ms 211624 KB Output is correct
7 Correct 216 ms 211516 KB Output is correct
8 Correct 176 ms 211268 KB Output is correct
9 Correct 172 ms 211264 KB Output is correct
10 Correct 197 ms 211136 KB Output is correct
11 Correct 218 ms 211528 KB Output is correct
12 Correct 272 ms 211756 KB Output is correct
13 Correct 205 ms 211528 KB Output is correct
14 Correct 4 ms 5836 KB Output is correct
15 Correct 168 ms 211704 KB Output is correct
16 Correct 251 ms 211932 KB Output is correct
17 Correct 167 ms 211388 KB Output is correct
18 Correct 161 ms 211496 KB Output is correct
19 Correct 238 ms 211580 KB Output is correct
20 Correct 192 ms 211260 KB Output is correct
21 Correct 212 ms 211436 KB Output is correct
22 Correct 269 ms 211368 KB Output is correct
23 Correct 194 ms 211524 KB Output is correct
24 Correct 280 ms 211528 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5836 KB Output is correct
2 Correct 264 ms 212020 KB Output is correct
3 Correct 217 ms 212144 KB Output is correct
4 Correct 160 ms 211464 KB Output is correct
5 Correct 170 ms 211496 KB Output is correct
6 Correct 243 ms 211624 KB Output is correct
7 Correct 216 ms 211516 KB Output is correct
8 Correct 176 ms 211268 KB Output is correct
9 Correct 172 ms 211264 KB Output is correct
10 Correct 197 ms 211136 KB Output is correct
11 Correct 218 ms 211528 KB Output is correct
12 Correct 272 ms 211756 KB Output is correct
13 Correct 205 ms 211528 KB Output is correct
14 Correct 4 ms 5836 KB Output is correct
15 Correct 168 ms 211704 KB Output is correct
16 Correct 251 ms 211932 KB Output is correct
17 Correct 167 ms 211388 KB Output is correct
18 Correct 161 ms 211496 KB Output is correct
19 Correct 238 ms 211580 KB Output is correct
20 Correct 192 ms 211260 KB Output is correct
21 Correct 212 ms 211436 KB Output is correct
22 Correct 269 ms 211368 KB Output is correct
23 Correct 194 ms 211524 KB Output is correct
24 Correct 280 ms 211528 KB Output is correct
25 Correct 148 ms 210864 KB Output is correct
26 Correct 224 ms 212012 KB Output is correct
27 Correct 176 ms 211388 KB Output is correct
28 Correct 173 ms 211380 KB Output is correct
29 Correct 242 ms 211768 KB Output is correct
30 Correct 202 ms 211508 KB Output is correct
31 Correct 197 ms 211264 KB Output is correct
32 Correct 313 ms 211396 KB Output is correct
33 Correct 1006 ms 211440 KB Output is correct
34 Correct 1262 ms 211364 KB Output is correct
35 Correct 1405 ms 211452 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5836 KB Output is correct
2 Correct 1259 ms 1670508 KB Output is correct
3 Correct 1079 ms 1670704 KB Output is correct
4 Correct 1027 ms 1672228 KB Output is correct
5 Correct 1153 ms 1672172 KB Output is correct
6 Correct 1071 ms 1670552 KB Output is correct
7 Correct 1074 ms 1668836 KB Output is correct
8 Correct 4 ms 5836 KB Output is correct
9 Correct 264 ms 212020 KB Output is correct
10 Correct 217 ms 212144 KB Output is correct
11 Correct 160 ms 211464 KB Output is correct
12 Correct 170 ms 211496 KB Output is correct
13 Correct 243 ms 211624 KB Output is correct
14 Correct 216 ms 211516 KB Output is correct
15 Correct 176 ms 211268 KB Output is correct
16 Correct 172 ms 211264 KB Output is correct
17 Correct 197 ms 211136 KB Output is correct
18 Correct 218 ms 211528 KB Output is correct
19 Correct 272 ms 211756 KB Output is correct
20 Correct 205 ms 211528 KB Output is correct
21 Correct 4 ms 5836 KB Output is correct
22 Correct 168 ms 211704 KB Output is correct
23 Correct 251 ms 211932 KB Output is correct
24 Correct 167 ms 211388 KB Output is correct
25 Correct 161 ms 211496 KB Output is correct
26 Correct 238 ms 211580 KB Output is correct
27 Correct 192 ms 211260 KB Output is correct
28 Correct 212 ms 211436 KB Output is correct
29 Correct 269 ms 211368 KB Output is correct
30 Correct 194 ms 211524 KB Output is correct
31 Correct 280 ms 211528 KB Output is correct
32 Correct 148 ms 210864 KB Output is correct
33 Correct 224 ms 212012 KB Output is correct
34 Correct 176 ms 211388 KB Output is correct
35 Correct 173 ms 211380 KB Output is correct
36 Correct 242 ms 211768 KB Output is correct
37 Correct 202 ms 211508 KB Output is correct
38 Correct 197 ms 211264 KB Output is correct
39 Correct 313 ms 211396 KB Output is correct
40 Correct 1006 ms 211440 KB Output is correct
41 Correct 1262 ms 211364 KB Output is correct
42 Correct 1405 ms 211452 KB Output is correct
43 Correct 1 ms 1612 KB Output is correct
44 Correct 4 ms 5852 KB Output is correct
45 Correct 1284 ms 1675376 KB Output is correct
46 Correct 1065 ms 1670928 KB Output is correct
47 Correct 1055 ms 1671224 KB Output is correct
48 Correct 1150 ms 1673200 KB Output is correct
49 Correct 1430 ms 1675384 KB Output is correct
50 Correct 1107 ms 1672924 KB Output is correct
51 Correct 1048 ms 1673228 KB Output is correct
52 Correct 972 ms 1671124 KB Output is correct
53 Correct 1715 ms 1671876 KB Output is correct
54 Correct 2179 ms 1672980 KB Output is correct
55 Correct 2467 ms 1671868 KB Output is correct
56 Correct 3573 ms 1672548 KB Output is correct
57 Correct 2564 ms 1672708 KB Output is correct
58 Correct 2850 ms 1672828 KB Output is correct
59 Correct 2465 ms 1672844 KB Output is correct
60 Correct 3809 ms 1672116 KB Output is correct
61 Correct 3701 ms 1672048 KB Output is correct