Submission #1217983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217983		hengliao	Dungeons Game (IOI21_dungeons)	C++20	25 / 100	7094 ms	103528 KiB

dungeons

#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

namespace{
    const ll mxN=4e5+5;
    const ll LOG=21;
    const ll inf=1e18;
    const ll dumb=6;

    ll n;
    ll s[mxN], p[mxN], w[mxN], l[mxN];
    array<ll, 2> up[mxN][LOG][dumb]; // des, sum
    vll con;
    ll siz;

    array<ll, 2> mrg(array<ll, 2> a, array<ll, 2> b){
        array<ll, 2> re;
        re[0]=b[0];
        re[1]=a[1]+b[1];
        return re;
    }

    array<ll, 3> mrg2(array<ll, 3> a, array<ll, 3> b){
        array<ll, 3> re;
        re[0]=b[0];
        re[1]=min(a[1], b[1]-a[2]);
        re[2]=a[2]+b[2];
        return re;
    }
}

void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
	n=N;
    for(ll i=0;i<=n;i++){
        s[i]=S[i];
        p[i]=P[i];
        w[i]=W[i];
        l[i]=L[i];
    }
    for(ll i=0;i<n;i++){
        con.pb(s[i]);
    }
    sort(con.begin(), con.end());
    con.erase(unique(con.begin(), con.end()), con.end());
        
    siz=con.size();

    for(ll i=0;i<=siz;i++){
        if(i<siz){
            for(ll j=0;j<n;j++){
                if(s[j]<con[i]){
                    up[j][0][i]={w[j], s[j]};
                }
                else{
                    up[j][0][i]={l[j], p[j]};
                }
            }
            up[n][0][i]={n, 0};
        }
        else{
            for(ll j=0;j<n;j++){
                up[j][0][i]={w[j], s[j]};
            }
            up[n][0][i]={n, 0};
        }
    }

    for(ll k=0;k<=siz;k++){
        for(ll j=1;j<LOG;j++){
            for(ll i=0;i<=n;i++){
                up[i][j][k]=mrg(up[i][j-1][k], up[up[i][j-1][k][0]][j-1][k]);
            }
        }
    }
}

long long simulate(int x, int z) {
    // cout<<"qrying "<<x<<' '<<z<<'\n';
	ll ans=z;
    while(x!=n){
        // cout<<"ans: "<<ans<<'\n';
        // cout<<"x: "<<x<<'\n';
        ll lev=0;
        for(ll i=0;i<siz;i++){
            if(ans>=con[i]) lev=i+1;
        }
        ll thr=inf;
        if(lev<siz){
            thr=con[lev];
        }
        // cout<<"lev: "<<lev<<'\n';
        // cout<<"thr: "<<thr<<'\n';
        for(ll i=LOG-1;i>=0;i--){
            if(ans+up[x][i][lev][1]<thr){
                // cout<<"going\n";
                ans+=up[x][i][lev][1];
                x=up[x][i][lev][0];
                // cout<<"ans: "<<ans<<'\n';
                // cout<<"x: "<<x<<'\n';
            }
        }
        // cout<<"ans: "<<ans<<'\n';
        // cout<<"x: "<<x<<'\n';
        ans+=up[x][0][lev][1];
        x=up[x][0][lev][0];
    }
    // cout<<"ans: "<<ans<<'\n';
    // cout<<"x: "<<x<<'\n';
    return ans;
}

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