# Aiuto Scale di Hogwarts

**URL:** <https://forum.olinfo.it/t/aiuto-scale-di-hogwarts/6780>\
**Category:** Aiuto\
**Created:** [12 Novembre 2021, 2:11pm UTC](https://forum.olinfo.it/t/aiuto-scale-di-hogwarts/6780 "2021-11-12T14:11:01Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![samuelemusiani](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/d9b06d/32.png) [@samuelemusiani](https://forum.olinfo.it/u/samuelemusiani)\
**Post date:** [12 Novembre 2021, 2:11pm UTC](https://forum.olinfo.it/t/aiuto-scale-di-hogwarts/6780/1 "2021-11-12T14:11:01Z")

</div>

Buongiorno, staveo cercando di risolvere [questo](https://training.olinfo.it/#/task/oii_hogwarts/statement) problema, ma sbaglio alcuni testcase banali e non capisco perché.

La mia idea era la seguente (e controllando [la soluzione ufficile](https://wiki-olinfo.chiodini.org/resources/2016_Nazionali.pdf) (p.14) mi sembra sia praticamente la stessa della soluzione **O(M log M)**):

1. Creo un grafo simile a quello che mi viene danto in input, cioè collego **A[i]** e **B[i]** con un arco visto che ci sarà prima o poi una scala che li collegherà

2. Il peso di questo arco però è dato da **inizio[i] + 1**, così, se per caso lo dovessi percorrere, so che impiegherò **inizio[i] + 1 + il tempo per arrivare a A[i]** ad arrivare a **B[i]**.

3. Faccio partire dijkstra sul grafo appena fatto e cerco la distanza dai nodi **0** e **N-1** , ma con un piccolo accorgimento: infatti quando espando un nodo e decido aggiornare i sui vicini, controllo che **il tempo impiegato per raggiungere il nodo su cui mi trovo sia minore della scoparsa dell’arco che collega ogni nodo vicino**. Se è così allora aggiorno la sua distanza e continuo con Dijkstra.

Sono consapevole che quando gli input diventano molto grandi è troppo lenta come soluzione, però la mia sbaglia anche su qualcuni input piccoli (es. testcase 005, 006, 007), quindi volevo sapere se il mio ragionamento aveva un senso o sto sbagliando qualcosa.

Ecco il codice:

```auto
struct tre{
    int nodo;
    int peso;
    int fine;
};

constexpr long long unsigned int INF = 1e15;

int raggiungi(int N, int M, int A[], int B[], int inizio[], int fine[]) {
    map<int, list<tre>> grafo;

    for(int i = 0; i < M; i++) {
        tre temp = {B[i], inizio[i] + 1, fine[i]};

        grafo[A[i]].push_back(temp);

        temp.nodo = A[i];
        grafo[B[i]].push_back(temp);
    }

    //dijkstra

    using p = pair<long long unsigned int, int>;

    priority_queue<p> q;

    vector<long long unsigned int> dist(N, INF);

    bitset<500001> visited;

    q.push({0, 0});
    dist[0] = 0;

    while(!q.empty()) {
        int nodo = q.top().second;
        q.pop();

        if(visited[nodo]) continue;

        visited[nodo] = 1;

        for(auto e: grafo[nodo]) {
            int b = e.nodo, w = e.peso;

            if(e.fine > dist[nodo] && dist[nodo] + w < dist[b]) {
                dist[b] = dist[nodo] + w;
                q.push({-dist[b], b});
            }
        }
    }

    return dist[N - 1] != INF ? dist[N - 1]: -1;
}

```

---

<div class="post-metadata">

**Author:** ![lollospadalaser](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/35a633/32.png) [@lollospadalaser](https://forum.olinfo.it/u/lollospadalaser)\
**Post date:** [13 Novembre 2021, 6:20pm UTC](https://forum.olinfo.it/t/aiuto-scale-di-hogwarts/6780/2 "2021-11-13T18:20:48Z")

</div>

La soluzione presentata dal testo ufficiale è quella O(M+T)  
Ti sconsiglio di usare il contenitore bitset perché è molto lento, non staresti nei tempi richiesti  
Questo dovrebbe essere quello che ti serve:

```auto
#include <list>
#include <limits>
#include <vector>
#include <queue>
#include <functional>
#include <iostream>
using namespace std;
struct arco{
    int nodo,inizio,fine;
};
bool visited[500000];
int raggiungi(int N, int M, int A[], int B[], int inizio[], int fine[]){
    list<arco> adj[N];
    vector<int> dist(N,numeric_limits<int>::max());
    typedef pair<int,int> ip;
    priority_queue<ip,vector<ip>,greater<ip>> q;
    for(int i=0;i<M;i++){
        arco temp={B[i],inizio[i],fine[i]};
        adj[A[i]].push_back(temp);
        temp.nodo=A[i];
        adj[B[i]].push_back(temp);
    }
    q.push({0,0});
    dist[0]=0;
    while(!q.empty()){
        int nodo=q.top().second;
        q.pop();
        if(visited[nodo])continue;
        visited[nodo]=true;
        for(list<arco>::iterator i=adj[nodo].begin();i!=adj[nodo].end();++i){
            int next=(*i).nodo;
            if((*i).fine>dist[nodo]){
                if((*i).inizio<dist[nodo]){
                    if(dist[nodo]+1<dist[next]){
                        dist[next]=dist[nodo]+1;
                        q.push({dist[next],next});
                    }
                }
                else if((*i).inizio+1<dist[next]){
                    dist[next]=(*i).inizio+1;
                    q.push({dist[next],next});
                }
            }
            //cout<<"nodo: "<<nodo<<" next: "<<next<<" dist nodo: "<<dist[nodo]<<" dist next: "<<dist[next]<<endl;
        }
    }
    //for(int i=0;i<N;i++)printf("%d: %d\n",i,dist[i]);
    if(dist[N-1]!=numeric_limits<int>::max()) return dist[N-1];
    return -1;
}

```

---

<div class="post-metadata">

**Author:** ![MyK\_00L](https://forum.olinfo.it/user_avatar/forum.olinfo.it/myk_00l/32/3000_2.png) [@MyK\_00L](https://forum.olinfo.it/u/MyK_00L)\
**Post date:** [14 Novembre 2021, 1:13pm UTC](https://forum.olinfo.it/t/aiuto-scale-di-hogwarts/6780/3 "2021-11-14T13:13:04Z")

</div>

> [@lollospadalaser](#):
>
> Ti sconsiglio di usare il contenitore bitset perché è molto lento

??!!??!!??!!??!!??!!

---

<div class="post-metadata">

**Author:** ![lollospadalaser](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/35a633/32.png) [@lollospadalaser](https://forum.olinfo.it/u/lollospadalaser)\
**Post date:** [14 Novembre 2021, 2:41pm UTC](https://forum.olinfo.it/t/aiuto-scale-di-hogwarts/6780/4 "2021-11-14T14:41:29Z")

</div>

in questo caso il bitset risulta più lento [questo](https://www.quora.com/In-C++-is-bitset-faster-than-an-array-of-bools) dovrebbe spiegarne il motivo. puoi provare cambiando dal codice

> [@lollospadalaser](#):
>
> `bool visited[500000];`

a bitset\<500000\> visited; vari test case falliranno con l’errore execution timed out.

---

<div class="post-metadata">

**Author:** ![MyK\_00L](https://forum.olinfo.it/user_avatar/forum.olinfo.it/myk_00l/32/3000_2.png) [@MyK\_00L](https://forum.olinfo.it/u/MyK_00L)\
**Post date:** [15 Novembre 2021, 12:28pm UTC](https://forum.olinfo.it/t/aiuto-scale-di-hogwarts/6780/5 "2021-11-15T12:28:04Z")

</div>

Sono d’accordo che bitset possa essere leggermente piu lento a volte (anche se spesso puo essere piu veloce perche’ fa meno cache miss), in ogni caso non dovrebbe neanche lontanamente essere cosi lento da mandarti in tle (a meno che non fossi gia a pochi millisecondi dal tle I guess).  
Comunque guardando la soluzione proposta se c’e’ da dire che qualche ds della stl e’ lenta piuttosto avrei detto quella `map<int, list<tre>>`

---

<div class="post-metadata">

**Author:** ![MyK\_00L](https://forum.olinfo.it/user_avatar/forum.olinfo.it/myk_00l/32/3000_2.png) [@MyK\_00L](https://forum.olinfo.it/u/MyK_00L)\
**Post date:** [15 Novembre 2021, 1:03pm UTC](https://forum.olinfo.it/t/aiuto-scale-di-hogwarts/6780/6 "2021-11-15T13:03:20Z")

</div>

Ho provato a modificare il codice il minimo possibile, il principale problema nella tua soluzione immagino fosse una comprensione sbagliata del testo: per fare una rampa di scale il tempo impiegato e’ 1 e puoi solo iniziare a percorrerla a inizio[i], tu aggiungevi inizio[i] come se fosse il tempo impiegato a percorrere le scale.  
Per questo motivo non erano necessari long long quindi gia che c’ero ho messo tutto a int.  
Sostituire la map con vector per il grafo risolve anche il problema dei TLE.  
Un paio di consigli:

- Usa `vector` al posto di `list`, list e’ generalmente inutile
- Usa `priority_queue<T,vector<T>,greater<T>>` per avere l’ordinamento dal piu piccolo cosi non devi stare a inserire le cose negate.
- Usa `array<int,2>` al posto di `pair<int,int>` per una sintassi meno pesante (volendo puoi fare uguale anche al posto delle struct se poi ti ricordi cosa sono i campi)
- per specificare `unsigned`, `long long`, `unsigned long long`, e altre cose del genere, non ti serve scriverci `int`
- fai `using ll = long long;` per avere i long long senza scrivere 9 caratteri (o better `using ll = int64_t;`), stessa cosa per le counterpart unsigned

```auto
#include <bits/stdc++.h>
using namespace std;

struct tre{
    int nodo;
    int peso;
    int fine;
};

const int INF = 1000000009;

int raggiungi(int N, int M, int A[], int B[], int inizio[], int fine[]) {
    vector<list<tre>> grafo(N+1);

    for(int i = 0; i < M; i++) {
        tre temp = {B[i], inizio[i], fine[i]};

        grafo[A[i]].push_back(temp);

        temp.nodo = A[i];
        grafo[B[i]].push_back(temp);
    }

    //dijkstra

    using p = pair<int, int>;

    priority_queue<p> q;

    vector<int> dist(N, INF);

    bitset<500001> visited;

    q.push({0, 0});
    dist[0] = 0;

    while(!q.empty()) {
        int nodo = q.top().second;
        q.pop();

        if(visited[nodo]) continue;

        visited[nodo] = 1;

        for(auto e: grafo[nodo]) {
            int b = e.nodo, w = e.peso;

            if(e.fine > dist[nodo] && max(dist[nodo],e.peso)+1<dist[b]) {
                dist[b] = max(dist[nodo],e.peso)+1;
                q.push({-dist[b], b});
            }
        }
    }

    return dist[N - 1] != INF ? dist[N - 1]: -1;
}

```

---

<div class="post-metadata">

**Author:** ![samuelemusiani](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/d9b06d/32.png) [@samuelemusiani](https://forum.olinfo.it/u/samuelemusiani)\
**Post date:** [15 Novembre 2021, 10:54pm UTC](https://forum.olinfo.it/t/aiuto-scale-di-hogwarts/6780/7 "2021-11-15T22:54:30Z")

</div>

Ahhh, ecco dove sbagliavo, era nella condizione finale del dijkstra!

Grazie mille, anche per i consigli su come alleggerire il codice