oj.uz

Submission #924877

# Submission time Handle Problem Language Result Execution time Memory
924877 2024-02-10T02:00:57 Z Programmer123 Dungeons Game (IOI21_dungeons) C++17
24 / 100
 7000 ms 1677168 KB 
#include "dungeons.h"
#include <bits/stdc++.h>

#define JUMP_SIZE 40
std::vector<int> s, p, w, l;
int N;
long long *minBlitz, *gainBlitz;
int **jumpTo;
__int128_t **jumpGain;
bool identical = true;

long long dp(int node, long long str);

long long calc(int node, long long str) {
    if (str >= s[node]) {
        return dp(w[node], str + s[node]);
    } else return dp(l[node], str + p[node]);
}

std::unordered_map<long long, long long> *cache;

long long dp(int node, long long str) {
    assert(node != N);
    if (str >= minBlitz[node]) return str + gainBlitz[node];
    if (!cache[node].count(str)) {
        cache[node][str] = calc(node, str);
    }
    return cache[node][str];
}

void init(int n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) {
    N = n;
    s = std::move(_s);
    p = std::move(_p);
    w = std::move(_w);
    l = std::move(_l);
    for (int i = 1; i < N; ++i) {
        if (s[i] != s[0]) identical = false;
    }
    minBlitz = new long long[N + 1];
    gainBlitz = new long long[N + 1];
    for (int i = 0; i <= N; ++i) {
        gainBlitz[i] = -1;
    }
    std::function<void(int)> calc = [&](int x) {
        if (gainBlitz[x] != -1) return;
        if (x == N) {
            minBlitz[x] = 0;
            gainBlitz[x] = 0;
            return;
        }
        calc(w[x]);
        minBlitz[x] = std::max(minBlitz[w[x]] - s[x], (long long) s[x]);
        gainBlitz[x] = gainBlitz[w[x]] + s[x];
    };
    for (int i = 0; i <= N; ++i) {
        calc(i);
    }
    cache = new std::remove_pointer<decltype(cache)>::type[N + 1];
#ifdef LOCAL
    std::cout << "minBlitz:";
    for (int i = 0; i <= N; ++i) {
        std::cout << " " << minBlitz[i];
    }
    std::cout << std::endl;
    std::cout << "gainBlitz:";
    for (int i = 0; i <= N; ++i) {
        std::cout << " " << gainBlitz[i];
    }
    std::cout << std::endl;
#endif
    jumpTo = new int *[N + 1];
    jumpGain = new __int128_t *[N + 1];
    for (int i = 0; i <= N; ++i) {
        jumpTo[i] = new int[JUMP_SIZE];
        jumpGain[i] = new __int128_t[JUMP_SIZE];
    }
    for (int i = 0; i < N; ++i) {
        jumpTo[i][0] = l[i];
        jumpGain[i][0] = p[i];
    }
    jumpTo[N][0] = N;
    jumpGain[N][0] = 0;
    for (int i = 1; i < JUMP_SIZE; ++i) {
        for (int j = 0; j <= N; ++j) {
            jumpTo[j][i] = jumpTo[jumpTo[j][i - 1]][i - 1];
            jumpGain[j][i] = jumpGain[j][i - 1] + jumpGain[jumpTo[j][i - 1]][i - 1];
        }
    }
}

long long simulate(int x, int _z) {
    __int128_t z = _z;
    if (identical) {
        if (z >= s[0]) return z + gainBlitz[x];
        for (int i = JUMP_SIZE - 1; i >= 0; --i) {
            if (z + jumpGain[x][i] <= s[0]) {
                z += jumpGain[x][i];
                x = jumpTo[x][i];
            }
        }
        while (z < s[0]) {
            if (x == N) return z;
            z += p[x];
            x = l[x];
        }
        return z + gainBlitz[x];
    }
    return dp(x, z);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 2140 KB Output is correct
4 Correct 55 ms 47956 KB Output is correct
5 Correct 3 ms 2908 KB Output is correct
6 Correct 56 ms 49488 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1368 KB Output is correct
2 Execution timed out 7147 ms 1677168 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 72 ms 48064 KB Output is correct
3 Correct 74 ms 49364 KB Output is correct
4 Correct 65 ms 49744 KB Output is correct
5 Correct 75 ms 49236 KB Output is correct
6 Correct 82 ms 48040 KB Output is correct
7 Correct 87 ms 48208 KB Output is correct
8 Correct 67 ms 49608 KB Output is correct
9 Correct 73 ms 48060 KB Output is correct
10 Correct 64 ms 49492 KB Output is correct
11 Correct 80 ms 48308 KB Output is correct
12 Correct 158 ms 49744 KB Output is correct
13 Correct 137 ms 49588 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 72 ms 48064 KB Output is correct
3 Correct 74 ms 49364 KB Output is correct
4 Correct 65 ms 49744 KB Output is correct
5 Correct 75 ms 49236 KB Output is correct
6 Correct 82 ms 48040 KB Output is correct
7 Correct 87 ms 48208 KB Output is correct
8 Correct 67 ms 49608 KB Output is correct
9 Correct 73 ms 48060 KB Output is correct
10 Correct 64 ms 49492 KB Output is correct
11 Correct 80 ms 48308 KB Output is correct
12 Correct 158 ms 49744 KB Output is correct
13 Correct 137 ms 49588 KB Output is correct
14 Correct 2 ms 1628 KB Output is correct
15 Correct 6901 ms 1159832 KB Output is correct
16 Correct 77 ms 53296 KB Output is correct
17 Correct 73 ms 54612 KB Output is correct
18 Execution timed out 7125 ms 1558848 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 72 ms 48064 KB Output is correct
3 Correct 74 ms 49364 KB Output is correct
4 Correct 65 ms 49744 KB Output is correct
5 Correct 75 ms 49236 KB Output is correct
6 Correct 82 ms 48040 KB Output is correct
7 Correct 87 ms 48208 KB Output is correct
8 Correct 67 ms 49608 KB Output is correct
9 Correct 73 ms 48060 KB Output is correct
10 Correct 64 ms 49492 KB Output is correct
11 Correct 80 ms 48308 KB Output is correct
12 Correct 158 ms 49744 KB Output is correct
13 Correct 137 ms 49588 KB Output is correct
14 Correct 2 ms 1628 KB Output is correct
15 Correct 6901 ms 1159832 KB Output is correct
16 Correct 77 ms 53296 KB Output is correct
17 Correct 73 ms 54612 KB Output is correct
18 Execution timed out 7125 ms 1558848 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1368 KB Output is correct
2 Execution timed out 7147 ms 1677168 KB Time limit exceeded
3 Halted 0 ms 0 KB -