oj.uz

Submission #924878

# Submission time Handle Problem Language Result Execution time Memory
924878 2024-02-10T02:15:45 Z Programmer123 Dungeons Game (IOI21_dungeons) C++17
36 / 100
 7000 ms 1668020 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;
std::vector<int> sValues;
std::vector<std::pair<int **, __int128_t **>> jumps;

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];
        }
    }
    std::set<int> svalues;
    for (int i = 0; i < N; ++i) {
        svalues.insert(s[i]);
    }
    for (auto x: svalues) {
        sValues.push_back(x);
    }
    if (sValues.size() <= 5) {
        for (int i = 0; i < sValues.size(); ++i) {
            auto to = new int *[N + 1];
            auto gain = new __int128_t *[N + 1];
            jumps.emplace_back(to, gain);
            for (int j = 0; j <= N; ++j) {
                to[j] = new int[JUMP_SIZE];
                gain[j] = new __int128_t[JUMP_SIZE];
            }
            int prev = 0;
            if (i) prev = sValues[i - 1];
            for (int j = 0; j < N; ++j) {
                if (s[j] > prev) {
                    to[j][0] = l[j];
                    gain[j][0] = p[j];
                } else {
                    to[j][0] = w[j];
                    gain[j][0] = s[j];
                }
            }
            to[N][0] = N;
            gain[N][0] = 0;
            for (int k = 1; k < JUMP_SIZE; ++k) {
                for (int j = 0; j <= N; ++j) {
                    to[j][k] = to[to[j][k - 1]][k - 1];
                    gain[j][k] = gain[j][k - 1] + gain[to[j][k - 1]][k - 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];
    }
    if (sValues.size() <= 5) {
        for (int _ = 0; _ < sValues.size(); ++_) {
            if (z < sValues[_]) {
                auto [to, gain] = jumps[_];
                for (int i = JUMP_SIZE - 1; i >= 0; --i) {
                    if (z + gain[x][i] <= sValues[_]) {
                        z += gain[x][i];
                        x = to[x][i];
                    }
                }
                while (z < sValues[_]) {
                    if (x == N) return z;
                    if (z >= s[x]) {
                        z += s[x];
                        x = w[x];
                    } else {
                        z += p[x];
                        x = l[x];
                    }
                }
            }
        }
        return z + gainBlitz[x];
    }
    return dp(x, z);
}

Compilation message

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:100:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for (int i = 0; i < sValues.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:149:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for (int _ = 0; _ < sValues.size(); ++_) {
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 2 ms 2140 KB Output is correct
4 Correct 60 ms 48576 KB Output is correct
5 Correct 3 ms 2904 KB Output is correct
6 Correct 61 ms 49412 KB Output is correct

Subtask #2
0.0 / 26.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2140 KB Output is correct
2 Correct 116 ms 89516 KB Output is correct
3 Correct 109 ms 90840 KB Output is correct
4 Correct 103 ms 91100 KB Output is correct
5 Correct 104 ms 90704 KB Output is correct
6 Correct 127 ms 89684 KB Output is correct
7 Correct 131 ms 89676 KB Output is correct
8 Correct 106 ms 91084 KB Output is correct
9 Correct 108 ms 89516 KB Output is correct
10 Correct 104 ms 90960 KB Output is correct
11 Correct 126 ms 89500 KB Output is correct
12 Correct 228 ms 89784 KB Output is correct
13 Correct 182 ms 89496 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2140 KB Output is correct
2 Correct 116 ms 89516 KB Output is correct
3 Correct 109 ms 90840 KB Output is correct
4 Correct 103 ms 91100 KB Output is correct
5 Correct 104 ms 90704 KB Output is correct
6 Correct 127 ms 89684 KB Output is correct
7 Correct 131 ms 89676 KB Output is correct
8 Correct 106 ms 91084 KB Output is correct
9 Correct 108 ms 89516 KB Output is correct
10 Correct 104 ms 90960 KB Output is correct
11 Correct 126 ms 89500 KB Output is correct
12 Correct 228 ms 89784 KB Output is correct
13 Correct 182 ms 89496 KB Output is correct
14 Correct 3 ms 4700 KB Output is correct
15 Correct 198 ms 172504 KB Output is correct
16 Correct 242 ms 214128 KB Output is correct
17 Correct 259 ms 256396 KB Output is correct
18 Correct 289 ms 256676 KB Output is correct
19 Correct 309 ms 257184 KB Output is correct
20 Correct 224 ms 174928 KB Output is correct
21 Correct 271 ms 216668 KB Output is correct
22 Correct 166 ms 132576 KB Output is correct
23 Correct 290 ms 215516 KB Output is correct
24 Correct 348 ms 174244 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2140 KB Output is correct
2 Correct 116 ms 89516 KB Output is correct
3 Correct 109 ms 90840 KB Output is correct
4 Correct 103 ms 91100 KB Output is correct
5 Correct 104 ms 90704 KB Output is correct
6 Correct 127 ms 89684 KB Output is correct
7 Correct 131 ms 89676 KB Output is correct
8 Correct 106 ms 91084 KB Output is correct
9 Correct 108 ms 89516 KB Output is correct
10 Correct 104 ms 90960 KB Output is correct
11 Correct 126 ms 89500 KB Output is correct
12 Correct 228 ms 89784 KB Output is correct
13 Correct 182 ms 89496 KB Output is correct
14 Correct 3 ms 4700 KB Output is correct
15 Correct 198 ms 172504 KB Output is correct
16 Correct 242 ms 214128 KB Output is correct
17 Correct 259 ms 256396 KB Output is correct
18 Correct 289 ms 256676 KB Output is correct
19 Correct 309 ms 257184 KB Output is correct
20 Correct 224 ms 174928 KB Output is correct
21 Correct 271 ms 216668 KB Output is correct
22 Correct 166 ms 132576 KB Output is correct
23 Correct 290 ms 215516 KB Output is correct
24 Correct 348 ms 174244 KB Output is correct
25 Correct 70 ms 51028 KB Output is correct
26 Correct 93 ms 54844 KB Output is correct
27 Correct 384 ms 121388 KB Output is correct
28 Correct 6637 ms 1275212 KB Output is correct
29 Correct 100 ms 57372 KB Output is correct
30 Execution timed out 7104 ms 1365480 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

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