Submission #821281

#	Time	Username	Problem	Language	Result	Execution time	Memory
821281		PixelCat	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3416 ms	1822664 KiB

dungeons

#include "dungeons.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

namespace {

    const int MAXN = 400'000;
    const int MAXLG = 25;
    const int INF = 1e15;
    const int BASE = 8;
    const int LAYERS = 9;

    int n;
    int vw[MAXN + 10];
    int vl[MAXN + 10];
    i32 nxtw[MAXN + 10];
    i32 nxtl[MAXN + 10];

    vector<i32> adj[MAXN + 10];
    
    struct Ayaya {
        int lo, hi;
        i32 nxt[MAXLG][MAXN + 10];
        int sum[MAXLG][MAXN + 10];
        int lose[MAXLG][MAXN + 10];  // must not >= this

        void init(int _lo, int _hi) {
            lo = _lo;
            hi = _hi;
            
            // build graph
            For(i, 0, n - 1) adj[i].clear();
            For(i, 0, n - 1) {
                i32 owo;
                if(lo >= vw[i]) {
                    owo = nxtw[i];
                    sum[0][i] = vw[i];
                    lose[0][i] = INF;
                } else {
                    owo = nxtl[i];
                    sum[0][i] = vl[i];
                    lose[0][i] = vw[i];
                }
                nxt[0][i] = owo;
                adj[owo].eb(i);
            }

            // binary lifting
            For(j, 1, MAXLG - 1) For(i, 0, n - 1) {
                nxt[j][i] = nxt[j - 1][nxt[j - 1][i]];
                sum[j][i] = sum[j - 1][i] + sum[j - 1][nxt[j - 1][i]];
                lose[j][i] = min(lose[j - 1][i], lose[j - 1][nxt[j - 1][i]] - sum[j - 1][i]);
            }
        }

        // {pos, val}
        pair<int, long long> solve(int pos, long long val) {
            if(pos == n || val > hi) return pii(pos, val);
            Forr(i, MAXLG - 1, 0) {
                if(lose[i][pos] > val) {
                    val += sum[i][pos];
                    pos = nxt[i][pos];
                }
                if(pos == n || val > hi) return pii(pos, val);
            }
            assert(val >= vw[pos]);
            val += vw[pos];
            pos = nxtw[pos];
            return pii(pos, val);
        }

        void out() {
            For(i, 0, n) cerr << nxt[0][i] << " \n"[i == n];
            For(i, 0, n) cerr << sum[0][i] << " \n"[i == n];
            For(i, 0, n) cerr << lose[0][i] << " \n"[i == n];
        }
    } aya[LAYERS];

    void _init(i32 N, vector<i32> s, vector<i32> p, vector<i32> w, vector<i32> l) {
        n = N;
        For(i, 0, n - 1) {
            vw[i] = s[i];
            vl[i] = p[i];
            nxtw[i] = w[i];
            nxtl[i] = l[i];
        }
        int lo = 1;
        int i = 0;
        for(; lo <= (int)1e7;) {
            int hi = lo * BASE;
            aya[i].init(lo, hi - 1);
            lo = hi;
            i++;
        }
        aya[i].init(lo, INF);
    }

    long long query(int pos, long long val) {
        int i = 0;
        while(pos != n) {
            For(_, 1, BASE) {
                tie(pos, val) = aya[i].solve(pos, val);
            }
            i++;
        }
        return val;
    }

}  // namespace

void init(i32 N, std::vector<i32> s, std::vector<i32> p, std::vector<i32> w, std::vector<i32> l) {
    ::_init(N, s, p, w, l);
}

long long simulate(i32 pos, i32 val) {
    return ::query(pos, val);
}

/*

3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3

24
25

*/

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