Submission #1082394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082394		SiliconSquared	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	96 ms	27972 KiB

dungeons

#include "dungeons.h"
using namespace std;
#include <vector>
#define LOG 25
#define X first
#define Y second
#define ll long long
int n;
struct dungeon{
    ll s,p,w,l,z;
    vector<pair<int,ll>> v;
    dungeon(){}
    dungeon(int _s,int _p,int _w,int _l){
        s=_s;p=_p;w=_w;l=_l;
        v.resize(LOG);
        v[0]={l,p};
    }
};
vector<dungeon> v;
void init(int _n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) {
    n=_n;
    v.resize(n);
    for (int i=0;i<n;i++){
        v[i]=dungeon(_s[i],_p[i],_w[i],_l[i]);
    }
    for (int i=n-1;i>=0;i--){
        v[i].z=v[i].s;
        if (v[i].w!=n){
            v[i].z+=v[v[i].w].z;
        }
    }
    for (int j=1;j<LOG;j++){
        for (int i=0;i<n;i++){
            if (v[i].v[j-1].X==n){
                v[i].v[j]=v[i].v[j-1];
            }else{
                v[i].v[j]={v[v[i].v[j-1].X].v[j-1].X,v[v[i].v[j-1].X].v[j-1].Y+v[i].v[j-1].Y};
            }
        }
    }
}

long long simulate(int x, int s) {
    ll z=s;
    for (int j=LOG-1;j>=0;j--){
        if (z+v[x].v[j].Y>v[0].s){continue;}
        z+=v[x].v[j].Y;
        x=v[x].v[j].X;
        if (x==n){break;}
    }
    if (z<v[0].s&&x!=n){
        z+=v[x].v[0].Y;
        x=v[x].v[0].X;
    }
    if (x!=n){
        z+=v[x].z;
    }
	return z;
}

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