제출 #791005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
791005		Trunkty	던전 (IOI21_dungeons)	C++17	0 / 100	7197 ms	1979552 KiB

dungeons

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll

#include "dungeons.h"

ll n;
ll s[50005],p[50005],w[50005],l[50005];
ll jump[50005][41][41],sumi[50005][41][41],mini[50005][41][41];

void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L){
    // may need to expand to 41, 1e18, ll
    n = N;
    for(ll i=1;i<=n;i++){
        s[i] = S[i-1];
        p[i] = P[i-1];
        w[i] = W[i-1]+1;
        l[i] = L[i-1]+1;
    }
    for(ll k=0;k<=40;k++){
        jump[n+1][0][k] = n+1;
        for(ll i=1;i<=n+1;i++){
            if(s[i]<(1LL<<k)){
                jump[i][0][k] = w[i];
                sumi[i][0][k] = s[i];
                mini[i][0][k] = 1e18;
            }
            else if(s[i]>=(1LL<<(k+1LL))){
                jump[i][0][k] = l[i];
                sumi[i][0][k] = p[i];
                mini[i][0][k] = 1e18;
            }
            else{
                jump[i][0][k] = l[i];
                sumi[i][0][k] = p[i];
                mini[i][0][k] = s[i];
            }
        }
    }
    for(ll k=0;k<=40;k++){
        for(ll j=1;j<=40;j++){
            for(ll i=1;i<=n+1;i++){
                jump[i][j][k] = jump[jump[i][j-1][k]][j-1][k];
                sumi[i][j][k] = sumi[i][j-1][k]+sumi[jump[i][j-1][k]][j-1][k];
                mini[i][j][k] = min(mini[i][j-1][k],mini[jump[i][j-1][k]][j][k]-sumi[i][j-1][k]);
            }
        }
    }

}

ll simulate(int x2, int z2){
    ll z = z2, x = x2+1;
    for(ll k=0;k<=40;k++){
        if(z<(1LL<<(k+1LL))){
            for(ll j=40;j>=0;j--){
                if(z+sumi[x][j][k]<(1LL<<(k+1LL)) and z<mini[x][j][k] and jump[x][j][k]!=n+1){
                    z += sumi[x][j][k];
                    x = jump[x][j][k];
                }
            }
            if(z>=s[x]){
                z += s[x];
                x = w[x];
            }
            else{
                z += p[x];
                x = l[x];
            }
            if(x==n+1){
                break;
            }
        }
    }
	return z;
}

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