Submission #826181

#	Time	Username	Problem	Language	Result	Execution time	Memory
826181		TheSahib	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	155 ms	325540 KiB

dungeons

#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 = 50005;
const int LOGMAX = 24;
const int startLog = 13;


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

struct G{
    array<ll, 3> par[LOGMAX + 1][MAX];
    void preCalc(){
        for (int j = 1; j <= LOGMAX; 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 = LOGMAX; j >= 0 && v != n; --j){
            ll a = start + par[j][v][1];
            if(a < target && (start + par[j][v][2] < 0)){
                start = a;
                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 + 1];

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){
        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(1e7 + 7);
    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(s < v[i + 1] && u != n){
            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:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for (int i = 0; i < v.size() - 1; i++)
      |                  ~~^~~~~~~~~~~~~~

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