Submission #439653

#	Time	Username	Problem	Language	Result	Execution time	Memory
439653		2qbingxuan	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	609 ms	1048580 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#ifdef local
#define debug(a...) qqbx(#a, a)
#define pary(a...) danb(#a, a)
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
template <typename ...T> void qqbx(const char *s, T ... a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\e[1;32m(" << s << ") = ("), ... ,(std::cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L) std::cerr << (f++ ? ", " : "") << *L;
    std::cerr << " ]\e[0m\n";
}
#else
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#define safe ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using ll = long long;
const ll INF = 1e18;
const int inf = 1e7, K = 5, PHASE = 10;
const int LG = 30, maxn = 400025;
struct node {
    ll p;
    int lim;
    int to;
    friend node operator+(const node &lhs, const node &rhs) {
        node res;
        res.p = min(INF, lhs.p + rhs.p);
        res.lim = max<ll>(0, min<ll>(lhs.lim, rhs.lim - lhs.p));
        res.to = rhs.to;
        return res;
    }
    node () : p(0), lim(inf), to(-1) {}
    node (ll _p, int _lim, int _to) : p(_p), lim(_lim), to(_to) {}
};
node st[3][maxn];
node nxt[LG][PHASE][maxn]; // 300 step, 90000 step
int n;
vector<int> s, p, w, l;
long long winwin[maxn];
void init(int _n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) {
    n = _n, s = _s, p = _p, w = _w, l = _l;
    st[0][n] = {0, 0, n};
    for (int lev = 0; lev < LG; lev++) {
        for (int i = 0; i < n; i++) {
            if (s[i] <= (1LL<<lev)) {
                nxt[lev][0][i] = { s[i], inf, w[i] };
            } else {
                nxt[lev][0][i] = { p[i], s[i], l[i] };
            }
        }
        nxt[lev][0][n] = { 0, 0, n };
        for (int phase = 1; phase < PHASE; phase++) {
            for (int i = 0; i < n; i++) st[0][i] = nxt[lev][phase-1][i];
            for (int i = 0; i <= n; i++) nxt[lev][phase][i].to = i;
            for (int L = 0; L < 3; L++) {
                if (K >> L & 1) {
                    for (int i = 0; i <= n; i++) {
                        auto &nd = nxt[lev][phase][i];
                        nd = nd + st[L][nd.to];
                    }
                }
                if (L+1 < 3) for (int i = 0; i <= n; i++) st[L+1][i] = st[L][i] + st[L][st[L][i].to];
            }
        }
    }
    winwin[n] = 0;
    for (int i = n-1; i >= 0; i--)
        winwin[i] = winwin[w[i]] + s[i];
    return;
}

long long simulate(int x, int _z) {
    long long z = _z;
    while (x != n && z < inf) {
        long long org_z = z;
        int lev = __lg(z);
        for (int phase = PHASE-1; phase >= 0; phase--) {
            for (int it = 0; it < K; it++) {
                if (z < nxt[lev][phase][x].lim) {
                    z += nxt[lev][phase][x].p;
                    x = nxt[lev][phase][x].to;
                }
            }
        }
        if (x == n)
            return z;
        assert (z >= s[x]);
        z += s[x];
        x = w[x];
        if (x == n)
            return z;
        // assert (__lg(z) > __lg(org_z));
    }
    return z + winwin[x];
}

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:83:19: warning: unused variable 'org_z' [-Wunused-variable]
   83 |         long long org_z = z;
      |                   ^~~~~

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