제출 #1241565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241565		Younis_Dwai	던전 (IOI21_dungeons)	C++20	26 / 100	465 ms	226632 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N=4e5+5;
long long sz,S[N],P[N],W[N],L[N],Sum[N][21],nxt[N][21],mx[N][21],d[N];
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l){
    sz=n;
    for(int i=1;i<=n;i++){
        S[i]=s[i-1];
        P[i]=p[i-1];
        W[i]=w[i-1];
        L[i]=l[i-1];
        W[i]++;
        L[i]++;
    }
    S[n+1]=0;
    L[n+1]=W[n+1]=1;
    for(int j=0;j<=20;j++){
        nxt[n+1][j]=n+1;
        mx[n+1][j]=1e18;
        Sum[n+1][j]=0;
    }
    for(int i=1;i<=n;i++){
        nxt[i][0]=W[i];
        Sum[i][0]=S[i];
        mx[i][0]=S[i];
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n+1;i++){
            nxt[i][j]=nxt[nxt[i][j-1]][j-1];
            Sum[i][j]=Sum[i][j-1]+Sum[nxt[i][j-1]][j-1];
            mx[i][j]=max(mx[i][j-1],mx[nxt[i][j-1]][j-1]);
        }
    }
    d[n+1]=0;
    for(int i=n;i>=1;i--){
        d[i]=1+d[W[i]];
    }
	return ;
}

long long simulate(int x, int z){
     ++x;
     long long power=z;
     while(x!=sz+1){
           int cnt=0;
           //cout<<" # "<<x<<' '<<power;
           for(int j=20;j>=0;j--){
               if(mx[x][j]>power || (1<<j)>d[x]) continue ;
               cnt+=(1<<j);
               power+=Sum[x][j];
               x=nxt[x][j];
           }
           if(x==sz+1) break ;
          // cout<<" % "<<x<<' '<<power<<' ';
           if(S[x]>power){
               power+=S[x];
               x=L[x];
           }
           else{
               power+=S[x];
               x=W[x];
           }
           //cout<<" $ "<<x<<' '<<power<<endl;

     }
     //cout<<endl;
	 return power;
}

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