Submission #826264

#	Time	Username	Problem	Language	Result	Execution time	Memory
826264		TheSahib	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2436 ms	1676772 KiB

dungeons

#pragma GCC optimize("O3")
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, ll>

const ll oo = 1e9 + 9;
const int MAX = 500005;
const int LOGMAX = 25;
const int liftMAX = 24;
const int startLog = 12;


int n;
vector<int> S, W, P, L;

struct G{
    array<ll, 3> par[liftMAX + 1][MAX];
    void preCalc(){
        for (int j = 1; j <= liftMAX; j++)
        {
            for (int i = 0; i <= n; i++)
            {
                int m = par[j - 1][i][0];
                par[j][i][0] = par[j - 1][m][0];
                par[j][i][1] = par[j - 1][i][1] + par[j - 1][m][1];
                par[j][i][2] = max(par[j - 1][i][2], par[j - 1][m][2] + par[j - 1][i][1]);
            }
        }
    }
    pii lift(ll start, ll target, int v){
        if(start >= target || v == n) return {v, start};
        for(int j = liftMAX; j >= 0 && v != n && start < target; --j){
            if(start + par[j][v][2] < 0){
                start = start + par[j][v][1];
                v = par[j][v][0];
            }
        }
        if(v == n){
            return {n, start};
        }
        if(start >= S[v]){
            start += S[v];
            v = W[v];
        }
        else{
            start += P[v];
            v = L[v];
        }
        return {v, start};
    }
};

vector<ll> v;
G gs[(LOGMAX - startLog + 2) / 2];

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;

    for(int i = startLog; i < LOGMAX; i += 2){
        v.push_back((1 << i));
    }
    
    for (int i = 0; i < v.size(); i++)
    {
        for(int j = 0; j <= N; ++j){
            if(j == N){
                gs[i].par[0][j] = {N, 0, -oo * oo};
                continue;
            }
            if(s[j] > v[i]){
                gs[i].par[0][j] = {l[j], p[j], p[j] - s[j]};
            }
            else{
                gs[i].par[0][j] = {w[j], s[j], -oo * oo};
            }
        }
        gs[i].preCalc();
    }
    v.push_back(oo * oo);
    return;
}

ll simulate(int x, int z) {
    ll u = x;
    ll s = z;
    while(s < (1 << startLog) && u != n){
        if(s >= S[u]){
            s += S[u];
            u = W[u];
        }
        else{
            s += P[u];
            u = L[u];
        }
    }
	for (int i = 0; i < v.size() - 1; i++)
    {
        while(u != n && s < v[i + 1]){
            pii p = gs[i].lift(s, v[i + 1], u);
            u = p.first;
            s = p.second;
        }
    }
    return s;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |  for (int i = 0; i < v.size() - 1; i++)
      |                  ~~^~~~~~~~~~~~~~

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