Submission #899001

#	Time	Username	Problem	Language	Result	Execution time	Memory
899001		Trisanu_Das	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2308 ms	1557932 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 400050;
const int L = 24;
const int K = 8;
const ll inf = (ll)1e18;

int n, nxt[K][L][N], S[N], W[N];
ll pw[K + 5], sum[K][L][N], mn[K][L][N], ft[N];
vector<pair<int, int>> E[N];

void DFS(int u, ll tot) {
    ft[u] = tot;
    for (auto e : E[u])
        DFS(e.first, tot + e.second);
}

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    ::n = n;
    for (int i = 0; i < n; i++)
        S[i] = s[i], W[i] = w[i];
    W[n] = n;
    S[n] = 0;

    pw[0] = 1;
    for (int i = 1; i <= K; i++)
        pw[i] = pw[i - 1] * 8;

    for (int i = 0; i < K; i++) {
        int h = pw[i];
        nxt[i][0][n] = n;
        sum[i][0][n] = 0;
        mn[i][0][n] = inf;

        for (int j = 0; j < n; j++) {
            if (s[j] <= h) {
                nxt[i][0][j] = w[j];
                sum[i][0][j] = s[j];
                mn[i][0][j] = inf;
            } else {
                nxt[i][0][j] = l[j];
                sum[i][0][j] = p[j];
                mn[i][0][j] = s[j];
            }
        }

        for (int j = 1; j < L; j++)
            for (int l = 0; l <= n; l++) {
                nxt[i][j][l] = nxt[i][j - 1][nxt[i][j - 1][l]];
                sum[i][j][l] = min(inf, sum[i][j - 1][l] + sum[i][j - 1][nxt[i][j - 1][l]]);
                mn[i][j][l] = min(mn[i][j - 1][l], mn[i][j - 1][nxt[i][j - 1][l]] - sum[i][j - 1][l]);
            }
    }

    for (int i = 0; i < n; i++)
        E[w[i]].push_back({i, s[i]});

    DFS(n, 0);
}

ll simulate(int x, int z) {
    ll h = z;

    for (int i = 0; i < K; i++) {
        while (1) {
            if (h >= pw[i + 1] || x == n)
                break;

            for (int j = L - 1; j >= 0; j--) {
                if (mn[i][j][x] > h) {
                    h += sum[i][j][x];
                    x = nxt[i][j][x];
                }
            }

            h += S[x];
            x = W[x];
        }
    }

    return h + ft[x];
}

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11