Submission #1185205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185205		PagodePaiva	던전 (IOI21_dungeons)	C++20	11 / 100	1494 ms	1199204 KiB

dungeons

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

using namespace std;

const int N = 50010;
const int LOGN = 16;
const int LOGT = 63;
long long s[N], p[N], w[N], l[N];

struct Binary_Lifting{
    struct Node{
        int pai;
        long long sum, val;
        Node(){
            pai = 0;
            sum = 0;
            val = 1e18;
        }
    } bin[N][LOGT][LOGN];
    void build(int n){
        for(int j = 0;j < LOGT;j++){
            long long c = (1LL<<j);
            for(int i = 0;i < n;i++){
                if(s[i] >= c){
                    bin[i][j][0].pai = l[i];
                    bin[i][j][0].sum = p[i];
                    bin[i][j][0].val = s[i];
                }
                else{
                    bin[i][j][0].pai = w[i];
                    bin[i][j][0].sum = s[i];
                    bin[i][j][0].val = 1e18;
                }
            }
            bin[n][j][0].pai = n;
            for(int bit = 1;bit < LOGN;bit++){
                for(int i = 0;i <= n;i++){
                    bin[i][j][bit].pai = bin[bin[i][j][bit-1].pai][j][bit-1].pai;
                    bin[i][j][bit].sum = bin[i][j][bit-1].sum + bin[bin[i][j][bit-1].pai][j][bit-1].sum;
                    bin[i][j][bit].val = min(bin[i][j][bit-1].val, bin[bin[i][j][bit-1].pai][j][bit-1].val - bin[i][j][bit-1].sum);
                }
            }
        }
    }
} bin;

void init(int n, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
    for(int i = 0;i < n;i++){
        s[i] = S[i];
        p[i] = P[i];
        w[i] = W[i];
        l[i] = L[i];
    }
    bin.build(n);
    return;
}

long long simulate(int x, int z) {
    long long ans = z, at = x;
    for(int j = 0;j < LOGT;j++){
        long long c = (1LL << j);
        for(int bit = LOGN-1;bit >= 0;bit--){
            if(bin.bin[at][j][bit].val <= ans){
                continue;
            }
            ans += bin.bin[at][j][bit].sum;
            at = bin.bin[at][j][bit].pai;
        }
    }
    return ans;
}

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