oj.uz

Submission #438280

# Submission time Handle Problem Language Result Execution time Memory
438280 2021-06-27T20:05:11 Z SHZhang Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 632648 KB 
#include "dungeons.h"
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long

int n;
ll s[400005];
ll p[400005];
int w[400005], l[400005];
// lvl i => [2^i, 2^(i+1))

int f[24][24][50005]; // in level i tree, node arrived at after 2^j moves from k
ll g[24][24][50005]; // in level i tree, strength gained by 2^j moves from k
ll h[24][24][50005]; // in level i tree, min init strength to win against opponent in
                      // current level after at most 2^j moves from k

ll upval[24][400005];
int upnode[24][400005];

vector<int> tree[400005];

ll ssum[400005];

int block[10000005];

int f2[19][400005]; // 2^i ancestor
ll g2[19][400005]; // 2^i total strength
ll h2[19][400005]; // min strength needed to not lose after 2^i

bool mode2;

void predfs(int node)
{
    if (node != n + 1) {
        ssum[node] = ssum[w[node]] + s[node];
    }
    for (int i = 0; i < tree[node].size(); i++) {
        predfs(tree[node][i]);
    }
}

void dfs(int node, int lvl, int bound)
{
    if (node == n + 1 || s[node] >= bound) {
        upval[lvl][node] = 0;
        upnode[lvl][node] = node;
    } else {
        upval[lvl][node] = upval[lvl][w[node]] + s[node];
        upnode[lvl][node] = upnode[lvl][w[node]];
    }
    for (int i = 0; i < tree[node].size(); i++) {
        dfs(tree[node][i], lvl, bound);
    }
}

void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
    for (int i = 0; i < 24; i++) {
        for (int j = (1 << i); j < min(1 << (i + 1), 10000001); j++) {
            block[j] = i;
        }
    }
    n = N;
    for (int i = 0; i < n; i++) {
        s[i+1] = S[i];
        p[i+1] = P[i];
        w[i+1] = W[i] + 1;
        l[i+1] = L[i] + 1;
    }
    for (int i = 1; i <= n; i++) {
        tree[w[i]].push_back(i);
    }
    predfs(n+1);
    mode2 = (n > 50000);
    if (mode2) {
        w[n+1] = n+1;
        for (int i = 1; i <= n + 1; i++) {
            f2[0][i] = w[i];
            g2[0][i] = s[i];
            h2[0][i] = s[i];
        }
        for (int pwr = 1; pwr < 19; pwr++) {
            for (int i = 1; i <= n + 1; i++) {
                f2[pwr][i] = f2[pwr-1][f2[pwr-1][i]];
                g2[pwr][i] = g2[pwr-1][i] + g2[pwr-1][f2[pwr-1][i]];
                h2[pwr][i] = max(h2[pwr-1][i], h2[pwr-1][f2[pwr-1][i]] - g2[pwr-1][i]);
            }
        }
        //fprintf(stderr, "HERE");
        return;
    }
    for (int lvl = 0; lvl < 24; lvl++) {
        dfs(n + 1, lvl, (1 << lvl));
        for (int i = 1; i <= n; i++) {
            if (s[i] < (1 << lvl)) continue;
            f[lvl][0][i] = upnode[lvl][l[i]];
            g[lvl][0][i] = p[i] + upval[lvl][l[i]];
            h[lvl][0][i] = s[i];
        }
        for (int pwr = 1; pwr < 24; pwr++) {
            for (int i = 1; i <= n; i++) {
                if (s[i] < (1 << lvl)) continue;
                int half = f[lvl][pwr-1][i];
                f[lvl][pwr][i] = f[lvl][pwr-1][half];
                g[lvl][pwr][i] = g[lvl][pwr-1][i] + g[lvl][pwr-1][half];
                h[lvl][pwr][i] = min(h[lvl][pwr-1][i],
                    h[lvl][pwr-1][half] - g[lvl][pwr-1][i]);
            }
        }
    }
}

long long simulate(int x, int Z) {
    x++;
    if (mode2) {
        ll curs = Z;
        while (true) {
            //fprintf(stderr, "%d %lld\n", x, curs);
            if (x == n + 1) return curs;
            if (curs < s[x]) {
                curs += p[x];
                x = l[x];
                //if (x == 0) return 123;
                continue;
            }
            for (int i = 18; i >= 0; i--) {
                if (curs >= h2[i][x]) {
                    curs += g2[i][x];
                    x = f2[i][x];
                }
                //if (x == 0) return 456;
                if (x == n + 1) return curs;
            }
        }
    }
    ll cur_s = Z;
    while (true) {
        if (x == n + 1) return cur_s;
        if (cur_s > 10000000) {
            cur_s += ssum[x];
            return cur_s;
        }
        int lvl = block[cur_s];
        if (s[x] < (1 << lvl)) {
            cur_s += upval[lvl][x];
            x = upnode[lvl][x]; continue;
        }
        if (s[x] <= cur_s) {
            cur_s += s[x];
            x = w[x]; continue;
        }
        for (int i = 23; i >= 0; i--) {
            if (cur_s < h[lvl][i][x]) {
                cur_s += g[lvl][i][x];
                x = f[lvl][i][x];
            }
            if (x == n + 1) return cur_s;
        }
    }
}

Compilation message

dungeons.cpp: In function 'void predfs(int)':
dungeons.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < tree[node].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~
dungeons.cpp: In function 'void dfs(int, int, int)':
dungeons.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < tree[node].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 53836 KB Output is correct
2 Correct 32 ms 53920 KB Output is correct
3 Correct 36 ms 54736 KB Output is correct
4 Correct 390 ms 396076 KB Output is correct
5 Correct 45 ms 67648 KB Output is correct
6 Correct 410 ms 395988 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 68720 KB Output is correct
2 Correct 453 ms 241092 KB Output is correct
3 Correct 405 ms 248428 KB Output is correct
4 Correct 401 ms 248316 KB Output is correct
5 Correct 529 ms 229952 KB Output is correct
6 Correct 455 ms 241120 KB Output is correct
7 Correct 423 ms 248388 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 67140 KB Output is correct
2 Correct 616 ms 584704 KB Output is correct
3 Correct 475 ms 610112 KB Output is correct
4 Correct 208 ms 141572 KB Output is correct
5 Correct 195 ms 163908 KB Output is correct
6 Correct 620 ms 584708 KB Output is correct
7 Correct 696 ms 608188 KB Output is correct
8 Correct 210 ms 164992 KB Output is correct
9 Correct 253 ms 138580 KB Output is correct
10 Correct 167 ms 118020 KB Output is correct
11 Correct 651 ms 608404 KB Output is correct
12 Correct 761 ms 631968 KB Output is correct
13 Correct 573 ms 631120 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 67140 KB Output is correct
2 Correct 616 ms 584704 KB Output is correct
3 Correct 475 ms 610112 KB Output is correct
4 Correct 208 ms 141572 KB Output is correct
5 Correct 195 ms 163908 KB Output is correct
6 Correct 620 ms 584708 KB Output is correct
7 Correct 696 ms 608188 KB Output is correct
8 Correct 210 ms 164992 KB Output is correct
9 Correct 253 ms 138580 KB Output is correct
10 Correct 167 ms 118020 KB Output is correct
11 Correct 651 ms 608404 KB Output is correct
12 Correct 761 ms 631968 KB Output is correct
13 Correct 573 ms 631120 KB Output is correct
14 Correct 37 ms 62148 KB Output is correct
15 Correct 388 ms 307576 KB Output is correct
16 Correct 613 ms 608224 KB Output is correct
17 Correct 284 ms 308036 KB Output is correct
18 Correct 304 ms 308608 KB Output is correct
19 Correct 689 ms 631644 KB Output is correct
20 Correct 337 ms 308588 KB Output is correct
21 Correct 335 ms 309188 KB Output is correct
22 Correct 620 ms 632648 KB Output is correct
23 Correct 644 ms 537968 KB Output is correct
24 Correct 737 ms 601540 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 67140 KB Output is correct
2 Correct 616 ms 584704 KB Output is correct
3 Correct 475 ms 610112 KB Output is correct
4 Correct 208 ms 141572 KB Output is correct
5 Correct 195 ms 163908 KB Output is correct
6 Correct 620 ms 584708 KB Output is correct
7 Correct 696 ms 608188 KB Output is correct
8 Correct 210 ms 164992 KB Output is correct
9 Correct 253 ms 138580 KB Output is correct
10 Correct 167 ms 118020 KB Output is correct
11 Correct 651 ms 608404 KB Output is correct
12 Correct 761 ms 631968 KB Output is correct
13 Correct 573 ms 631120 KB Output is correct
14 Correct 37 ms 62148 KB Output is correct
15 Correct 388 ms 307576 KB Output is correct
16 Correct 613 ms 608224 KB Output is correct
17 Correct 284 ms 308036 KB Output is correct
18 Correct 304 ms 308608 KB Output is correct
19 Correct 689 ms 631644 KB Output is correct
20 Correct 337 ms 308588 KB Output is correct
21 Correct 335 ms 309188 KB Output is correct
22 Correct 620 ms 632648 KB Output is correct
23 Correct 644 ms 537968 KB Output is correct
24 Correct 737 ms 601540 KB Output is correct
25 Correct 554 ms 630908 KB Output is correct
26 Correct 610 ms 631820 KB Output is correct
27 Correct 282 ms 168688 KB Output is correct
28 Correct 265 ms 168708 KB Output is correct
29 Correct 660 ms 631696 KB Output is correct
30 Correct 237 ms 171392 KB Output is correct
31 Correct 259 ms 171396 KB Output is correct
32 Correct 707 ms 514500 KB Output is correct
33 Correct 1120 ms 632400 KB Output is correct
34 Correct 1725 ms 609004 KB Output is correct
35 Correct 933 ms 631908 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 68720 KB Output is correct
2 Correct 453 ms 241092 KB Output is correct
3 Correct 405 ms 248428 KB Output is correct
4 Correct 401 ms 248316 KB Output is correct
5 Correct 529 ms 229952 KB Output is correct
6 Correct 455 ms 241120 KB Output is correct
7 Correct 423 ms 248388 KB Output is correct
8 Correct 41 ms 67140 KB Output is correct
9 Correct 616 ms 584704 KB Output is correct
10 Correct 475 ms 610112 KB Output is correct
11 Correct 208 ms 141572 KB Output is correct
12 Correct 195 ms 163908 KB Output is correct
13 Correct 620 ms 584708 KB Output is correct
14 Correct 696 ms 608188 KB Output is correct
15 Correct 210 ms 164992 KB Output is correct
16 Correct 253 ms 138580 KB Output is correct
17 Correct 167 ms 118020 KB Output is correct
18 Correct 651 ms 608404 KB Output is correct
19 Correct 761 ms 631968 KB Output is correct
20 Correct 573 ms 631120 KB Output is correct
21 Correct 37 ms 62148 KB Output is correct
22 Correct 388 ms 307576 KB Output is correct
23 Correct 613 ms 608224 KB Output is correct
24 Correct 284 ms 308036 KB Output is correct
25 Correct 304 ms 308608 KB Output is correct
26 Correct 689 ms 631644 KB Output is correct
27 Correct 337 ms 308588 KB Output is correct
28 Correct 335 ms 309188 KB Output is correct
29 Correct 620 ms 632648 KB Output is correct
30 Correct 644 ms 537968 KB Output is correct
31 Correct 737 ms 601540 KB Output is correct
32 Correct 554 ms 630908 KB Output is correct
33 Correct 610 ms 631820 KB Output is correct
34 Correct 282 ms 168688 KB Output is correct
35 Correct 265 ms 168708 KB Output is correct
36 Correct 660 ms 631696 KB Output is correct
37 Correct 237 ms 171392 KB Output is correct
38 Correct 259 ms 171396 KB Output is correct
39 Correct 707 ms 514500 KB Output is correct
40 Correct 1120 ms 632400 KB Output is correct
41 Correct 1725 ms 609004 KB Output is correct
42 Correct 933 ms 631908 KB Output is correct
43 Correct 45 ms 50540 KB Output is correct
44 Correct 42 ms 68752 KB Output is correct
45 Correct 587 ms 229940 KB Output is correct
46 Correct 587 ms 230120 KB Output is correct
47 Correct 5467 ms 229984 KB Output is correct
48 Correct 1515 ms 241188 KB Output is correct
49 Correct 584 ms 229912 KB Output is correct
50 Correct 448 ms 241004 KB Output is correct
51 Execution timed out 7093 ms 238412 KB Time limit exceeded
52 Halted 0 ms 0 KB -