Submission #818645

#	Time	Username	Problem	Language	Result	Execution time	Memory
818645		PixelCat	던전 (IOI21_dungeons)	C++17	25 / 100	230 ms	278836 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 = 50'000;
const int MAXLG = 25;
const int INF = 1e15;

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

struct Ayaya {
    int lo, hi;
    vector<int> adj[MAXN + 10];
    int nxt[MAXLG + 5][MAXN + 10];
    int sum[MAXLG + 5][MAXN + 10];
    int win[MAXN + 10];

    void init(int _lo, int _hi) {
        lo = _lo;
        hi = _hi;
        
        // build graph
        For(i, 0, n - 1) {
            int owo, val;
            if(lo >= vw[i]) { owo = nxtw[i]; val = vw[i]; }
            else            { owo = nxtl[i]; val = vl[i]; }
            nxt[0][i] = owo;
            sum[0][i] = val;
            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]];
        }

        // win without promotion?
        For(i, 0, n - 1) win[i] = INF;
        win[n] = 0;
        queue<int> que;
        que.emplace(n);
        while(!que.empty()) {
            int cur = que.front(); que.pop();
            for(auto &i:adj[cur]) {
                win[i] = win[cur] + sum[0][i];
                que.emplace(i);
            }
        }

        // cerr << lo << " ~ " << hi << "\n";
        // For(i, 0, n - 1) {
        //     cerr << nxt[0][i] << " \n"[i == n - 1];
        // }
        // For(i, 0, n) {
        //     cerr << win[i] << " \n"[i == n];
        // }
    }

    // {pos, val}
    pii solve(int pos, int val) {
        if(pos == n || val > hi) return pii(pos, val);
        if(val + win[pos] <= hi) return pii(n, val + win[pos]);
        Forr(i, MAXLG - 1, 0) {
            if(val + sum[i][pos] <= hi) {
                val += sum[i][pos];
                pos = nxt[i][pos];
            }
        }
        val += sum[0][pos];
        pos = nxt[0][pos];
        return pii(pos, val);
    }
} aya[6];

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];
    }
    vector<int> lims(all(s));
    lims.eb(0);
    lims.eb(INF);
    sort(all(lims));
    lims.erase(unique(all(lims)), lims.end());
    For(i, 0, sz(lims) - 2) aya[i].init(lims[i], lims[i + 1] - 1);
    m = sz(lims) - 1;
}

int query(int pos, int val) {
    For(i, 0, m - 1) {
        tie(pos, val) = aya[i].solve(pos, val);
        // cerr << pos << " " << val << "\n";
    }
    // cerr << "\n";
    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: 0 / 11
• Subtask 2: 0 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11