IOI 2021 - Dungeons

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// IOI 2021 - Dungeons
// Binary lifting with strength threshold levels.
// At level k (threshold 2^k), precompute fast-forward through all opponents
// with s[i] < 2^k (guaranteed win). Use binary lifting for O(log n) per step.

const int MAXN = 400005;
const int LEVELS = 25;
const int LOG = 25;

int n;
int s_val[MAXN], p_val[MAXN], w_val[MAXN], l_val[MAXN];

// nxt[k][j][i] = destination after 2^j win-steps at level k
// gain[k][j][i] = total strength gained in those steps
int nxt[LEVELS][LOG][MAXN];
ll gain[LEVELS][LOG][MAXN];

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_val[i] = s[i];
        p_val[i] = p[i];
        w_val[i] = w[i];
        l_val[i] = l[i];
    }

    for (int k = 0; k < LEVELS; k++) {
        ll threshold = 1LL << k;
        // Base case: one step at level k
        for (int i = 0; i <= n; i++) {
            if (i == n) {
                nxt[k][0][i] = n;
                gain[k][0][i] = 0;
            } else if (s_val[i] < threshold) {
                // Guaranteed win: gain s[i], go to w[i]
                nxt[k][0][i] = w_val[i];
                gain[k][0][i] = s_val[i];
            } else {
                // Cannot fast-forward: stop
                nxt[k][0][i] = i;
                gain[k][0][i] = 0;
            }
        }
        // Binary lifting
        for (int j = 1; j < LOG; j++) {
            for (int i = 0; i <= n; i++) {
                int mid = nxt[k][j - 1][i];
                nxt[k][j][i] = nxt[k][j - 1][mid];
                gain[k][j][i] = gain[k][j - 1][i] + gain[k][j - 1][mid];
            }
        }
    }
}

ll simulate(int x, int z) {
    ll strength = z;
    int dungeon = x;

    while (dungeon != n) {
        // Find highest level where we can fast-forward
        int k = 0;
        while (k < LEVELS - 1 && (1LL << (k + 1)) <= strength) k++;

        // Fast-forward through winnable opponents at this level
        bool moved = false;
        for (int j = LOG - 1; j >= 0; j--) {
            int nd = nxt[k][j][dungeon];
            ll ng = gain[k][j][dungeon];
            if (nd != dungeon) {
                if (strength + ng < (1LL << (k + 1)) || k == LEVELS - 1) {
                    strength += ng;
                    dungeon = nd;
                    moved = true;
                }
            }
        }

        if (!moved) {
            if (dungeon == n) break;
            // Handle single encounter
            if (strength >= s_val[dungeon]) {
                strength += s_val[dungeon];
                dungeon = w_val[dungeon];
            } else {
                strength += p_val[dungeon];
                dungeon = l_val[dungeon];
            }
        }
    }

    return strength;
}

int main() {
    int _n, q;
    scanf("%d %d", &_n, &q);
    vector<int> s(_n), p(_n), w(_n), l(_n);
    for (int i = 0; i < _n; i++)
        scanf("%d %d %d %d", &s[i], &p[i], &w[i], &l[i]);
    init(_n, s, p, w, l);
    while (q--) {
        int x, z;
        scanf("%d %d", &x, &z);
        printf("%lld\n", simulate(x, z));
    }
    return 0;
}

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{listings}
\usepackage{geometry}
\usepackage{hyperref}
\geometry{margin=2.5cm}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\bfseries,
  breaklines=true,
  numbers=left,
  numberstyle=\tiny,
  frame=single,
  tabsize=2
}

\title{IOI 2021 -- Dungeons}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Summary}
There are $n$ dungeons (indexed $0$ to $n-1$) and a final dungeon $n$. Each dungeon $i$ has:
\begin{itemize}
  \item $s[i]$: opponent strength
  \item $p[i]$: strength gain if you lose
  \item $w[i]$: next dungeon if you win ($w[i] > i$)
  \item $l[i]$: next dungeon if you lose
\end{itemize}

If you win (your strength $\ge s[i]$), gain $s[i]$ strength and go to $w[i]$. If you lose, gain $p[i]$ strength and go to $l[i]$.

Given starting dungeon and initial strength, simulate until reaching dungeon $n$. Return final strength.

\section{Solution Approach}

\subsection{Binary Lifting with Threshold Grouping}
Direct simulation is $O(n)$ per query in the worst case. We use binary lifting with strength thresholds.

\subsubsection{Key Idea}
Group operations by strength thresholds. Define $T = \lceil \log_2(\max s[i]) \rceil$ threshold levels: $2^0, 2^1, \ldots, 2^T$.

For threshold level $k$ (threshold $= 2^k$): if the hero's strength $\ge 2^k$, they win against all opponents with $s[i] < 2^k$. Pre-compute ``fast forwarding'' through dungeons where all opponents have $s[i] < 2^k$.

\subsubsection{Preprocessing}
For each level $k$ and dungeon $i$, compute:
\begin{itemize}
  \item $\text{nxt}[k][i]$: the dungeon reached after following the path from $i$ until encountering an opponent with $s[i] \ge 2^k$ (or reaching dungeon $n$).
  \item $\text{gain}[k][i]$: total strength gained along this path.
\end{itemize}

This is done using binary lifting: $\text{nxt}[k][i]$ and $\text{gain}[k][i]$ for $2^j$ steps.

\subsubsection{Query Processing}
For a query with starting dungeon $d$ and strength $z$:
\begin{enumerate}
  \item Find the lowest level $k$ such that $z \ge 2^k$.
  \item Fast-forward through all opponents with $s < 2^k$.
  \item After gaining strength, $z$ may exceed $2^{k+1}$; move to the next level.
  \item Repeat until reaching dungeon $n$.
\end{enumerate}

\section{C++ Solution}

\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 400005;
const int LEVELS = 25; // log2(max strength)
const int LOG = 25;    // binary lifting depth

int n;
int s_val[MAXN], p_val[MAXN], w_val[MAXN], l_val[MAXN];

// For each level k, nxt[k][j][i] = destination after 2^j steps at level k
// gain[k][j][i] = strength gained after 2^j steps at level k
int nxt[LEVELS][LOG][MAXN];
ll gain[LEVELS][LOG][MAXN];

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_val[i] = s[i];
        p_val[i] = p[i];
        w_val[i] = w[i];
        l_val[i] = l[i];
    }

    for (int k = 0; k < LEVELS; k++) {
        ll threshold = 1LL << k;
        // Base case (1 step at level k):
        // If strength >= threshold and at dungeon i:
        //   If s[i] < threshold: we definitely win -> gain s[i], go to w[i]
        //   If s[i] >= threshold: we stop (can't fast-forward)
        for (int i = 0; i <= n; i++) {
            if (i == n) {
                nxt[k][0][i] = n;
                gain[k][0][i] = 0;
            } else if (s_val[i] < threshold) {
                // Win: gain s[i], go to w[i]
                nxt[k][0][i] = w_val[i];
                gain[k][0][i] = s_val[i];
            } else {
                // Can't fast-forward: stop here
                nxt[k][0][i] = i;
                gain[k][0][i] = 0;
            }
        }

        // Binary lifting
        for (int j = 1; j < LOG; j++) {
            for (int i = 0; i <= n; i++) {
                int mid = nxt[k][j-1][i];
                nxt[k][j][i] = nxt[k][j-1][mid];
                gain[k][j][i] = gain[k][j-1][i] + gain[k][j-1][mid];
            }
        }
    }
}

ll simulate(int x, int z) {
    ll strength = z;
    int dungeon = x;

    while (dungeon != n) {
        // Find appropriate level
        int k = 0;
        while (k < LEVELS - 1 && (1LL << (k + 1)) <= strength) k++;
        // strength >= 2^k but < 2^(k+1) (or k = LEVELS-1)

        // Fast-forward through opponents with s < 2^k
        // But at level k, we can only skip opponents with s < 2^k.
        // We want the highest level where we can skip.

        if (k >= LEVELS) k = LEVELS - 1;

        // Try to fast-forward at level k
        bool moved = false;
        for (int j = LOG - 1; j >= 0; j--) {
            int nd = nxt[k][j][dungeon];
            ll ng = gain[k][j][dungeon];
            if (nd != dungeon) {
                // Check we don't overshoot (strength stays < 2^(k+1) to stay in level k)
                // Actually, gaining strength only helps. Just apply.
                if (strength + ng < (1LL << (k + 1)) || k == LEVELS - 1) {
                    strength += ng;
                    dungeon = nd;
                    moved = true;
                }
            }
        }

        if (!moved) {
            // We're at an opponent with s[dungeon] >= 2^k
            // or strength has grown past 2^(k+1)
            if (dungeon == n) break;

            if (strength >= s_val[dungeon]) {
                // Win
                strength += s_val[dungeon];
                dungeon = w_val[dungeon];
            } else {
                // Lose
                strength += p_val[dungeon];
                dungeon = l_val[dungeon];
            }
        }
    }

    return strength;
}

int main() {
    int _n, q;
    scanf("%d %d", &_n, &q);
    vector<int> s(_n), p(_n), w(_n), l(_n);
    for (int i = 0; i < _n; i++)
        scanf("%d %d %d %d", &s[i], &p[i], &w[i], &l[i]);
    init(_n, s, p, w, l);
    while (q--) {
        int x, z;
        scanf("%d %d", &x, &z);
        printf("%lld\n", simulate(x, z));
    }
    return 0;
}
\end{lstlisting}

\section{Complexity Analysis}
\begin{itemize}
  \item \textbf{Preprocessing:} $O(n \cdot L \cdot \log n)$ where $L = O(\log(\max s))$ is the number of threshold levels.
  \item \textbf{Per query:} $O(L \cdot \log n)$ -- we pass through at most $L$ levels (strength can at most double $L$ times), and at each level, the binary lifting takes $O(\log n)$.
  \item \textbf{Space:} $O(n \cdot L \cdot \log n)$.
\end{itemize}

\end{document}