Submission #827327

#	Time	Username	Problem	Language	Result	Execution time	Memory
827327		TahirAliyev	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	175 ms	121320 KiB

dungeons

#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 = 5e4 + 5, LOGMAX = 25;



int N;
vector<ll> S;

struct g{
    pii 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].first;
                par[j][i].first = par[j - 1][m].first;
                par[j][i].second = par[j - 1][i].second + par[j - 1][m].second;
            }
        }
    }
    pii lift(int u, int s, ll t){
        if(u == N || s >= t){
            return {u, s};
        }
        
        ll curs = s;
        int v = u;
        for (int j = LOGMAX - 1; j >= 0; j--)
        {
            if(curs + par[j][v].second < t){
                curs += par[j][v].second;
                v = par[j][v].first;
            }
        }
        return make_pair(par[0][v].first, par[0][v].second + curs);
    }
};


g G[7];

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

    set<int> tmp;
    for (int i = 0; i < N; i++) tmp.insert(s[i]);
    S.push_back(-1);
    for(int a : tmp) S.push_back(a);

    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]};
            }
            else{
                G[j].par[0][i] = {l[i], p[i]};
            }
        }
    }
    S.push_back(oo);
    
    
    for (int j = 0; j < 6; j++)
    {
        G[j].par[0][n] = {n, 0};
        G[j].init();
    }
}

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

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