Submission #1003049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003049		irmuun	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	96 ms	22652 KiB

dungeons

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

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int N=4e5+5;

int n;
vector<int>s,p,w,l,cnt;
int nxt[N][30];
ll inc[N][30];

void init(int N,vector<int>S,vector<int>P,vector<int>W,vector<int>L){
    n=N;
    s=S;
    p=P;
    w=W;
    l=L;
    cnt.resize(n+1);
    cnt[n]=0;
    for(int i=n-1;i>=0;i--){
        cnt[i]=cnt[w[i]]+1;
    }
    nxt[n][0]=n;
    inc[n][0]=0;
    for(int i=0;i<n;i++){
        nxt[i][0]=l[i];
        inc[i][0]=p[i];
    }
    for(int j=1;j<30;j++){
        for(int i=0;i<=n;i++){
            nxt[i][j]=nxt[nxt[i][j-1]][j-1];
            inc[i][j]=inc[i][j-1]+inc[nxt[i][j-1]][j-1];
        }
    }
}

bool check(int x,ll z,int u){
    for(int j=29;j>=0;j--){
        if(u&(1<<j)){
            z+=inc[x][j];
            x=nxt[x][j];
        }
    }
    return (z>=s[0]||x==n);
}
void ADD(int &x,ll &z,int u){
    for(int j=29;j>=0;j--){
        if(u&(1<<j)){
            z+=inc[x][j];
            x=nxt[x][j];
        }
    }
}

ll simulate(int x,int Z){
    ll z=Z;
    ll L=0,R=(1<<29);
    while(L<R){
        ll mid=(L+R)/2;
        if(check(x,z,mid)){
            R=mid;
        }
        else{
            L=mid+1;
        }
    }
    ADD(x,z,L);
    return z+(ll)cnt[x]*(ll)s[0];
}

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