Énoncé¶
Bienvenue dans le Donjon de Prolobeuk !
Le donjon est composé d'une multitude de salles numérotées de 0 à N. La salle 0 est la sortie du donjon. La salle de départ n'est pas déterminée.
N portes existent pour passer d'une salle à une autre, et il n'existe qu'un seul chemin entre deux salles : la structure du donjon ressemble donc à un arbre.
Chaque porte dispose d'un identifiant unique et d'un nombre de serrures. Une porte peut être soit ouverte, soit fermée, auquel cas il est nécessaire de disposer d'au moins autant de clés que de serrures pour pouvoir ouvrir la porte. Lors de l'ouverture d'une ou de plusieurs portes, vous conservez les clés : votre nombre de clés reste donc constant du début à la fin de votre parcours.
Lorsque vous entrez dans le donjon, il vous est assigné une salle de départ et une plage. Vous commencez donc dans la salle de départ et votre objectif est d'atteindre la sortie. La plage qui vous est assignée détermine quelles portes sont ouvertes et quelles portes sont fermées : Toute porte ayant un identifiant compris entre les deux bornes de la plage (incluses) est fermée lors de votre arrivée. Toutes les autres portes sont ouvertes.
Il vous sera posé une série de requêtes, auxquelles il faudra répondre dans l'ordre. Une requête contient votre salle de départ, ainsi que les deux bornes permettant de déterminer quelles portes sont fermées. Pour chaque requête, vous devez afficher le nombre minimum de clés nécessaires pour atteindre la sortie du donjon.
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : N, nombre de portes.
- Sur la ligne suivante, un entier : R, nombre de requêtes.
- Sur les lignes suivantes, une liste de N éléments : portes, liste des
portes entre les salles.
- Une ligne par élément de la liste : séparés par des espaces, un entier salle1 (première salle), un entier salle2 (seconde salle), un entier serrures (nombre de clés nécessaires pour ouvrir la porte si elle est fermée), et un entier id (l'identifiant unique de la porte).
- Sur les lignes suivantes, une liste de R éléments : requetes, liste
des requêtes.
- Une ligne par élément de la liste : séparés par des espaces, un entier salle (salle de départ), un entier id min (l'identifiant minimal des portes fermées), et un entier id max (l'identifiant maximal des portes fermées).
Sortie¶
Pour chaque requête, afficher le nombre de clés nécessaires au minimum pour atteindre la sortie
Contraintes¶
- $0 \le N \le 1\,000$
- $0 \le R \le 1\,000$
- $0 \le id \le 200\,000$
- $0 \le serrures \le 10^9$
- Tous les $id$ sont uniques
Contraintes de performance¶
- $0 \le N \le 100\,000$
- $0 \le R \le 100\,000$