oj.uz

Submission #442835

# Submission time Handle Problem Language Result Execution time Memory
442835 2021-07-09T08:29:18 Z SorahISA Dungeons Game (IOI21_dungeons) C++17
13 / 100
 160 ms 24324 KB 
#include "dungeons.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long
// #define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

namespace {

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

// const int maxn = 4E5 + 5;
const int maxn = 5E4 + 5;
// const int w_lgmx = 19;
const int w_lgmx = 16 + 1;
const int l_lgmx = 24 + 1;

int N;
vector<int> S, P, W, L;

vector<int> dep(maxn);

// int win_anc[w_lgmx][maxn], win_sum[w_lgmx][maxn], win_val[w_lgmx][maxn];
int los_anc[l_lgmx][maxn], los_sum[l_lgmx][maxn];

} /// end of namespace

void init(int32_t _N, vector<int32_t> _S, vector<int32_t> _P, vector<int32_t> _W, vector<int32_t> _L) {
    N = _N;
    for (auto &x : _S) S.eb(x);
    for (auto &x : _P) P.eb(x);
    for (auto &x : _W) W.eb(x);
    for (auto &x : _L) L.eb(x);
    S.eb(0), P.eb(0), W.eb(N), L.eb(N);
    
    // memset(win_anc, 0x00, sizeof(win_anc));
    // memset(win_sum, 0x00, sizeof(win_sum));
    // memset(win_val, 0x00, sizeof(win_val));
    memset(los_anc, 0x00, sizeof(los_anc));
    memset(los_sum, 0x00, sizeof(los_sum));
    
    for (int i = N-1; i >= 0; --i) dep[i] = dep[W[i]] + S[i];
    
    for (int i = 0; i <= N; ++i) {
        // win_anc[0][i] = W[i];
        // win_sum[0][i] = S[i];
        // win_val[0][i] = S[i];
        los_anc[0][i] = L[i];
        los_sum[0][i] = P[i];
    }
    
    // for (int lay = 1; lay < w_lgmx; ++lay) {
        // for (int i = 0; i <= N; ++i) {
            // int win_par = win_anc[lay-1][i];
            // win_anc[lay][i] = win_anc[lay-1][win_par];
            // win_sum[lay][i] = win_sum[lay-1][i] + win_sum[lay-1][win_par];
            // win_val[lay][i] = max(win_val[lay-1][i], win_val[lay-1][win_par]);
        // }
    // }
    
    for (int lay = 1; lay < l_lgmx; ++lay) {
        for (int i = 0; i <= N; ++i) {
            int los_par = los_anc[lay-1][i];
            los_anc[lay][i] = los_anc[lay-1][los_par];
            los_sum[lay][i] = los_sum[lay-1][i] + los_sum[lay-1][los_par];
        }
    }
}

int simulate(int32_t now, int32_t _Z) {
    /// s[i] = s[j] ///
    int Z = _Z;
    if (Z >= S[now]) return Z + dep[now];
    for (int lay = l_lgmx-1; lay >= 0; --lay) {
        if (Z + los_sum[lay][now] < S[now]) {
            Z += los_sum[lay][now];
            now = los_anc[lay][now];
        }
        // cerr << "(Z, now): " << Z << "," << now << "\n";
    }
    Z += P[now], now = L[now];
    return Z + dep[now];
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20172 KB Output is correct
2 Incorrect 10 ms 20172 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 20300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20276 KB Output is correct
2 Correct 65 ms 24324 KB Output is correct
3 Correct 72 ms 24212 KB Output is correct
4 Correct 57 ms 24264 KB Output is correct
5 Correct 67 ms 24264 KB Output is correct
6 Correct 90 ms 24264 KB Output is correct
7 Correct 84 ms 24264 KB Output is correct
8 Correct 57 ms 24288 KB Output is correct
9 Correct 56 ms 24264 KB Output is correct
10 Correct 62 ms 24276 KB Output is correct
11 Correct 56 ms 24292 KB Output is correct
12 Correct 160 ms 24288 KB Output is correct
13 Correct 130 ms 24288 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20276 KB Output is correct
2 Correct 65 ms 24324 KB Output is correct
3 Correct 72 ms 24212 KB Output is correct
4 Correct 57 ms 24264 KB Output is correct
5 Correct 67 ms 24264 KB Output is correct
6 Correct 90 ms 24264 KB Output is correct
7 Correct 84 ms 24264 KB Output is correct
8 Correct 57 ms 24288 KB Output is correct
9 Correct 56 ms 24264 KB Output is correct
10 Correct 62 ms 24276 KB Output is correct
11 Correct 56 ms 24292 KB Output is correct
12 Correct 160 ms 24288 KB Output is correct
13 Correct 130 ms 24288 KB Output is correct
14 Incorrect 11 ms 20296 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20276 KB Output is correct
2 Correct 65 ms 24324 KB Output is correct
3 Correct 72 ms 24212 KB Output is correct
4 Correct 57 ms 24264 KB Output is correct
5 Correct 67 ms 24264 KB Output is correct
6 Correct 90 ms 24264 KB Output is correct
7 Correct 84 ms 24264 KB Output is correct
8 Correct 57 ms 24288 KB Output is correct
9 Correct 56 ms 24264 KB Output is correct
10 Correct 62 ms 24276 KB Output is correct
11 Correct 56 ms 24292 KB Output is correct
12 Correct 160 ms 24288 KB Output is correct
13 Correct 130 ms 24288 KB Output is correct
14 Incorrect 11 ms 20296 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 20300 KB Output isn't correct
2 Halted 0 ms 0 KB -