Submission #1174320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174320		PagodePaiva	Dungeons Game (IOI21_dungeons)	C++20	37 / 100	7096 ms	328420 KiB

dungeons

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

using namespace std;

const long long N = 400010;
const long long LOGN = 30;

struct Binary_Lifting{
    long long pai[N][LOGN], val[N][LOGN], mx[N][LOGN];
    void build(long long n){
        for(long long bit = 1;bit < LOGN;bit++){
            for(long long i = 0;i <= n;i++){
                pai[i][bit] = pai[pai[i][bit-1]][bit-1];
                val[i][bit] = val[i][bit-1] + val[pai[i][bit-1]][bit-1];
                mx[i][bit] = max(mx[i][bit-1], -val[i][bit-1]+mx[pai[i][bit-1]][bit-1]);
            }
        }
    }
} bin;
map <int, int> comprimir;
long long pai_ruim[N], val_ruim[N];
int n;

void init(int nn, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
    n = nn;
    vector <array <int, 5>> sortar;
    for(int i = 0;i < n;i++){
        sortar.push_back({s[i], p[i], w[i], l[i], i});
    }
    sort(sortar.begin(), sortar.end());
    int con = 0;
    for(auto [a, b, c, d, i] : sortar){
        comprimir[i] = con;
        con++;
    }
    comprimir[con] = con;
    con++;
    for(auto &[a, b, c, d, i] : sortar){
      //  cout << i << ' ' << comprimir[i] << '\n';
        c = comprimir[c];
        d = comprimir[d];
        pai_ruim[comprimir[i]] = d;
        val_ruim[comprimir[i]] = b;
    }
    bin.pai[0][0] = sortar[0][2];
    bin.val[0][0] = sortar[0][0];
    bin.mx[0][0] = sortar[0][0];
    for(int i = 1;i < n;i++){
        if(sortar[i][2] > i){
            bin.pai[i][0] = sortar[i][2];
            bin.val[i][0] = sortar[i][0];
            bin.mx[i][0] = sortar[i][0];
        }
        else{
            int p = sortar[i][2];
            int v = sortar[i][0];
            v += bin.val[p][0];
            p = bin.pai[p][0];
            bin.pai[i][0] = p;
            bin.val[i][0] = v;
            bin.mx[i][0] = sortar[i][0];
        }
    }
    bin.pai[n][0] = n;
    bin.val[n][0] = 0;
    bin.mx[n][0] = -1e18;
    bin.build(n);
}

long long simulate(int st, int z) {
    long long res = z;
    st = comprimir[st];
   // cout << st << '\n';
    while(st != n){
        for(int bit = LOGN-1;bit >= 0;bit--){
            if(res >= bin.mx[st][bit]){
              //  cout << st << '\n';
               // cout << bit << ' ' << st << ' ' << res << ' ' << bin.pai[st][bit] << ' ' << bin.mx[st][bit] << '\n';
                res += bin.val[st][bit];
                st = bin.pai[st][bit];
            }   
        }
        if(st == n) break;
        res += val_ruim[st];
        st = pai_ruim[st];
    }
    return res;
}

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