Submission #825408

#	Time	Username	Problem	Language	Result	Execution time	Memory
825408		TheSahib	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	7103 ms	707644 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

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

const int MAX = 50005;
const int LOGMAX = 24;
const int oo = 1e9 + 9;


int n;
vector<int> S, W;

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]);
            }
        }
    }
    pii lift(ll start, ll target, int v){
        if(start >= target || v == n) return {v, start};
        for(int j = LOGMAX; j >= 0; --j){
            ll a = start + par[j][v][1];
            if(a < target && (par[j][v][2] <= (target >> 1) || par[j][v][2] > a)){
                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 += par[0][v][1];
            v = par[0][v][0];
        }
        return {v, start};
    }
};

vector<ll> v;
G gs[LOGMAX];

void init(int N, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    n = N;
    S = s;
    W = w;

    for(int i = 0; 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, 0};
                continue;
            }
            if(s[j] > v[i]){
                gs[i].par[0][j] = {l[j], p[j], s[j]};
            }
            else{
                gs[i].par[0][j] = {w[j], s[j], s[j]};
            }
        }
        gs[i].preCalc();
    }
    v.push_back(1ll * oo * oo);
    return;
}

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

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