제출 #1286199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286199		edo	던전 (IOI21_dungeons)	C++20	100 / 100	3636 ms	1720684 KiB

dungeons

#include <bits/stdc++.h>

using namespace std;
using ll   = long long;
using vi   = vector<int>;
using vll  = vector<ll>;
using vvi  = vector<vi>;
using vvll = vector<vll>;
using pii  = pair<int,int>;
using pll  = pair<ll,ll>;
using ui    = unsigned int;
using ull   = unsigned long long;
using pui   = pair<ui,ui>;
using pull  = pair<ull,ull>;

template<typename T>
using vc = std::vector<T>;


#define YES cout << "YES\n"
#define NO  cout << "NO\n"
#define yes cout << "yes\n"
#define no  cout << "no\n"
#define Yes cout << "Yes\n"
#define No  cout << "No\n"

template<typename T> void sc(T &x) { cin >> x; }
template<typename T, typename U> void sc(pair<T,U> &p) { sc(p.first), sc(p.second); }
template<typename T> void sc(vector<T> &v) { for (auto &x : v) sc(x); }
template<typename... A> void sc(A&... a) { (sc(a), ...); }


template<typename T> void _pt(const T &x){cout << x;}
template<typename T, typename U> void _pt(const pair<T,U> &p){_pt(p.first); cout << ' '; _pt(p.second);}
template<typename T> void _pt(const vector<T> &v){bool f=1; for(auto &x:v){if(!f) cout<<' '; _pt(x); f=0;}}
template<typename... A> void pt(const A&... a){(_pt(a), ...);}


template<typename T, typename U> bool umin(T &a, const U &b) { return b < a ? (a = b, true) : false; }
template<typename T, typename U> bool umax(T &a, const U &b) { return b > a ? (a = b, true) : false; }

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define FOR1(n)            for (int i=0; i<(n); ++i)
#define FOR2(i,n)          for (int i=0; i<(n); ++i)
#define FOR3(i,l,r)        for (int i=(l); i<(r); ++i)
#define FOR4(i,l,r,k)      for (int i=(l); i<(r); i+=(k))
#define FOR(...)           GET_MACRO(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define ROF1(n)            for (int i=(n)-1; i>=0; --i)
#define ROF2(i,n)          for (int i=(n)-1; i>=0; --i)
#define ROF3(i,l,r)        for (int i=(r)-1; i>=(l); --i)
#define ROF4(i,l,r,k)      for (int i=(r)-1; i>=(l); i-=(k))
#define ROF(...)           GET_MACRO(__VA_ARGS__, ROF4, ROF3, ROF2, ROF1)(__VA_ARGS__)
#define all(c)   (c).begin(), (c).end()
#define allr(c)  (c).rbegin(), (c).rend()
#define eb       emplace_back
#define mp       make_pair
#define mt       make_tuple
#define fi       first
#define se       second
#define pb       push_back
#define trav(x,a) for (auto &x : (a))
#define sz(a) ((int)(a).size())
#define mem(a,v) memset(a, v, sizeof(a))
#define nl pt("\n")

#include "dungeons.h"
const int MN = 400000 + 5;
const int B = 11;  
const int ML = 8; 
ll pc[ML];           
int n;
vi w, l, s, g;
const ll inf = LLONG_MAX;

struct LiftNode {
    int to;  
    ll add;
    ll need;
    LiftNode(): to(0), add(0), need(inf) {}
    LiftNode(int _to, ll _add, ll _need): to(_to), add(_add), need(_need) {}
};

// lift[level_index][binary_pow_index][node] => LiftNode
vc<vc<vc<LiftNode>>> lift;

void init(int N, vi s_, vi p_, vi w_, vi l_) {
    n = N;
    w = w_;
    l = l_;
    s = s_;
    g = p_;
    w.pb(n);
    l.pb(n);
    s.pb(0);
    g.pb(0);

    pc[0] = 1;
    FOR(i, 1, ML) {
        if (pc[i-1] > inf / B) pc[i] = inf / 2;
        else pc[i] = pc[i-1] * B;
    }

    int logn = (n > 1) ? __lg(n) + 2 : 2;

    lift.assign(ML, vc<vc<LiftNode>>(logn, vc<LiftNode>(n + 1)));

    FOR(lvl, ML) {
        lift[lvl][0][n] = LiftNode(n, 0, inf);
        FOR(node, n) {
            if ((ll)s[node] >= pc[lvl]) {
                lift[lvl][0][node] = LiftNode(l[node], (ll)g[node], (ll)s[node]);
            } 
            else {
                lift[lvl][0][node] = LiftNode(w[node], (ll)s[node], inf);
            }
        }
    }

    FOR(lvl, ML) {
        FOR(j, 1, logn) {
            FOR(node, n + 1) {
                const LiftNode &L = lift[lvl][j-1][node];
                const LiftNode &R = lift[lvl][j-1][L.to];
                int new_to = R.to;
                ll new_add = L.add + R.add;
                ll new_need;
                if (L.need == inf) {
                    if (R.need == inf) new_need = inf;
                    else {
                        ll adjusted = R.need - L.add;
                        if (adjusted <= 0) new_need = 0;
                        else new_need = adjusted;
                    }
                } 
                else {
                    if (R.need == inf) new_need = L.need;
                    else {
                        ll adjusted = R.need - L.add;
                        if (adjusted <= 0) new_need = min(L.need, 0LL);
                        else new_need = min(L.need, adjusted);
                    }
                }
                lift[lvl][j][node] = LiftNode(new_to, new_add, new_need);
            }
        }
    }
}

ll simulate(int x, int Z) {
    int cur = x;
    ll ans = (ll)Z;
    while (cur != n) {
        int level = 0;
        FOR(ML) {
            if (pc[i] <= ans) level = i;
            else break;
        }
        int logn = sz(lift[level]);

        ll upperBound = (level + 1 < ML) ? pc[level + 1] : inf;
        while (cur != n && ans < upperBound) {
            ROF(j, logn) {
                const LiftNode &node = lift[level][j][cur];
                if (node.need > ans || node.need == inf) {
                    ans += node.add;
                    cur = node.to;
                    if (cur == n) break;
                }
            }
            if (cur == n) break;

            if (ans >= (ll)s[cur]) {
                ans += (ll)s[cur];
                cur = w[cur];
            } 
            else {
                ans += (ll)g[cur];
                cur = l[cur];
            }
        }
    }
    return ans;
}


// int32_t main() {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);

//     init(3, {2, 6, 9}, {3, 1, 2}, {2, 2, 3}, {1, 0, 1});
//     pt(simulate(0, 1)); nl;  
//     pt(simulate(2, 3)); nl;  
//     return 0;
// }

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