Submission #624940

#	Time	Username	Problem	Language	Result	Execution time	Memory
624940		leaked	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2916 ms	571748 KiB

dungeons

#include <bits/stdc++.h>
#include "dungeons.h"

#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}

const int N=400'000+1;
const int lt=19;
const int c=6;

int up[N][c][lt];
int mn[N][c][lt];
int go[N][c][lt];

ll pode[N];
int ok=0;
int w[N],s[N],p[N],l[N];
int n;
vec<int> kek;


vec<int> ps;

void clever_init(){
    int pw=32;
    ps.pb(1);
    while(ps.back()<=(1e7)) ps.pb(ps.back()*pw);
    int lv=sz(ps);
    for(int i=n;i>=0;i--){
        pode[i]=pode[w[i]]+s[i];
    }
//    cout<<lv<<endl;
    for(int j=0;j+1<lv;j++){
        for(int i=0;i<=n;i++){
            if(s[i]>ps[j]&&s[i]<=(ps[j+1])){
                mn[i][j][0]=s[i];
                go[i][j][0]=l[i];
                up[i][j][0]=p[i];
            }
            else if(s[i]<=ps[j]){
                go[i][j][0]=w[i];
                up[i][j][0]=s[i];
                mn[i][j][0]=1e9;
            }
            else{
                go[i][j][0]=l[i];
                up[i][j][0]=p[i];
                mn[i][j][0]=1e9;
            }
        }
        for(int st=1;st<lt;st++){
            for(int i=0;i<=n;i++){
                mn[i][j][st]=min(mn[i][j][st-1],mn[go[i][j][st-1]][j][st-1]-up[i][j][st-1]);
                go[i][j][st]=go[go[i][j][st-1]][j][st-1];
                up[i][j][st]=min(ps.back(),up[i][j][st-1]+up[go[i][j][st-1]][j][st-1]);
            }
        }
    }
}

ll clever_query(int x,int z){
    ll sm=z;
    int t=upper_bound(all(ps),sm)-ps.begin()-1;
    while(sm<kek.back() && x!=n){
        while(sm>=(ps[t+1])) ++t;
        for(int j=lt-1;j>=0;j--){
            if(mn[x][t][j]>sm && (sm+up[x][t][j])<=kek.back() && (sm+up[x][t][j])<(ps[t+1])){
                sm+=up[x][t][j];
                x=go[x][t][j];
            }
        }
        if(sm<s[x]){
            sm+=p[x];
            x=l[x];
        }
        else{
            sm+=s[x];
            x=w[x];
        }
    }
    if(x!=n) assert(sm>=kek.back());
    sm+=pode[x];

    return sm;
}
void init(int n, vec<int> a,vec<int> b,vec<int> c,vec<int> d){
    for(int i=0;i<n;i++){
        s[i]=a[i];
        p[i]=b[i];
        w[i]=c[i];
        l[i]=d[i];
    }
    s[n]=0;w[n]=n;l[n]=n;p[n]=0;

    ::n=n;
    for(int i=0;i<n;i++) kek.pb(s[i]);
    sort(all(kek));kek.erase(unique(all(kek)),kek.end());

    clever_init();
}

long long simulate(int x, int z){
    return clever_query(x,z);
}


/*
3 2
13 13 13
4 3 1
2 2 3
1 0 1
0 1
2 3

*/

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