Submission #827643

#	Time	Username	Problem	Language	Result	Execution time	Memory
827643		TahirAliyev	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2365 ms	1741044 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 = 1e18;

const int MAX = 400004, LOGMAX = 26;

const int logStart = 12, INC = 2;

int N;
vector<ll> S;
vector <int> st, P, W, L;

struct g{
    array<ll, 3> par[LOGMAX][MAX];
    void init(){
        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][i][1] + par[j - 1][m][2]);
            }
        }
    }
    pii lift(int u, ll s, ll t){
        if(u == N || s >= t){
            return {u, s};
        }
        
        ll curs = s;
        int v = u;
        for (int j = LOGMAX - 1; j >= 0 && curs < t && v != N; j--)
        {
            if(curs + par[j][v][2] < 0){
                curs += par[j][v][1];
                v = par[j][v][0];
            }
        }
        if(v == N) return {v, curs};
        if(st[v] <= curs){
            return make_pair(W[v], st[v] + curs);
        }
        else{
            return make_pair(L[v], P[v] + curs);
        }
    }
};


g G[(LOGMAX - logStart) / INC];

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    N = n;
    st = s;
    P = p;
    W = w;
    L = l;
    for (int i = logStart; i < LOGMAX; i += INC)
    {
        S.push_back(1ll << i);
    }

    for (int j = 0; j < S.size(); j++)
    {
        for (int i = 0; i < n; i++)
        {
            if(s[i] <= S[j]){
                G[j].par[0][i] = {w[i], s[i], -oo};
            }
            else{
                G[j].par[0][i] = {l[i], p[i], -s[i]};
            }
        }
    }
    
    for (int j = 0; j < S.size(); j++)
    {
        G[j].par[0][n] = {n, 0, -oo};
        G[j].init();
    }
    
    S.push_back(oo);
}

ll simulate(int x, int z) {
    ll X = x, Z = z;
    while(Z < (1 << logStart) && X != N){
        if(Z >= st[X]){
            Z += st[X];
            X = W[X];
        }
        else{
            Z += P[X];
            X = L[X];
        }
    }
	for (int i = 0; i < S.size() - 1; i++)
    {
        while(Z < S[i + 1] && X != N){
            pii a = G[i].lift(X, Z, S[i + 1]);
            X = a.first, Z = a.second;
        }
    }
    return Z;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int j = 0; j < S.size(); j++)
      |                     ~~^~~~~~~~~~
dungeons.cpp:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for (int j = 0; j < S.size(); j++)
      |                     ~~^~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for (int i = 0; i < S.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