제출 #1284743

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284743		edo	던전 (IOI21_dungeons)	C++20	0 / 100	7093 ms	30912 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"
int n;
vi s, p, w, l;
vll base, U;
const int nax = 400000;
const int LOG = 20;

vvi next_win;
vvll gain_win;
vvi next_lose;
vvll gain_lose;

const ll inf = 4e18;

void init(int _n, vi _s, vi _p, vi _w, vi _l) {
    n = _n;
    s = _s;
    p = _p;
    w = _w;
    l = _l;
    base.resize(n + 1);
    U.resize(n + 1);
    base.at(n) = 0;
    U.at(n) = 0;
    ROF(n) {
        base.at(i) = s.at(i) + base.at(w.at(i));
        U.at(i) = max((ll)s.at(i), U.at(w.at(i)) - s.at(i));
    }

    int logn = 64 - __builtin_clzll(n + 1);
    next_win.resize(n, vi(logn));
    gain_win.resize(n, vll(logn));
    next_lose.resize(n, vi(logn));
    gain_lose.resize(n, vll(logn));
    
    FOR(n) {
        next_win[i][0] = w[i];
        gain_win[i][0] = s[i];
        next_lose[i][0] = l[i];
        gain_lose[i][0] = p[i];
    }
    
    FOR(j, 1, logn) {
        FOR(n) {
            int mid = next_win[i][j-1];
            next_win[i][j] = (mid < n) ? next_win[mid][j-1] : n;
            gain_win[i][j] = gain_win[i][j-1] + ((mid < n) ? gain_win[mid][j-1] : 0);
            
            int mid_lose = next_lose[i][j-1];
            next_lose[i][j] = (mid_lose < n) ? next_lose[mid_lose][j-1] : n;
            gain_lose[i][j] = gain_lose[i][j-1] + ((mid_lose < n) ? gain_lose[mid_lose][j-1] : 0);
        }
    }
}

ll simulate(int x, int z) {
    ll ans = z;
    int cur = x;
    while(cur != n && ans < U.at(cur)) {
        if(ans >= s.at(cur)) {
            int logn = sz(next_win[0]);
            ROF(j, logn) {
                if (next_win[cur][j] < n && 
                    ans + gain_win[cur][j] < U.at(next_win[cur][j])) {
                    ans += gain_win[cur][j];
                    cur = next_win[cur][j];
                }
            }
            if (cur < n && ans >= s.at(cur)) {
                ans += s.at(cur);
                cur = w.at(cur);
            }   
        }
        else {
            int logn = sz(next_lose[0]);
            ROF(j, logn) {
                if (next_lose[cur][j] < n && 
                    ans + gain_lose[cur][j] < s.at(next_lose[cur][j]) &&
                    ans + gain_lose[cur][j] < U.at(next_lose[cur][j])) {
                    ans += gain_lose[cur][j];
                    cur = next_lose[cur][j];
                }
            }
            if (cur < n && ans < s.at(cur)) {
                ans += p.at(cur);
                cur = l.at(cur);
            }
        }
    }
    if (cur == n) 
        return ans;
    
    else 
        return ans + base.at(cur);
    
}


// 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: 0 / 11
• Subtask 2: 0 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11