Le donjon de Prolobeuk – Épreuve régionale 2022

Niveau 7

É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$

Contraintes d'exécution

Utilisation mémoire maximum
200000 kilo-octets
Temps d'exécution maximum
2000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
4
5
0 1 10 3
1 2 5 0
2 3 3 5
4 2 8 2
0 0 10
1 3 3
1 4 7
3 0 10
4 0 2
Exemple de sortie
0
10
0
10
8
Commentaire

Pour la première requête, vous commencez déjà sur la salle de sortie. Aucune clé n'est donc nécessaire pour l'atteindre.

Pour la deuxième requête, la porte d'identifiant 3 est la seule fermée, et c'est la seule porte vous séparant de la sortie. Vous aurez donc besoin de l'ouvrir en vous servant de 10 clés.

Pour la troisième requête, les portes d'identifiants compris entre 4 et 7 sont les seules fermées. La porte 3 étant la seule vous séparant de la sortie, elle est donc déjà ouverte. Vous n'avez donc pas besoin de clé pour atteindre la sortie.

Pour la 4e requête, toutes les portes sont fermées, et vous partez de la salle 3. Vous devez donc passer par la porte 5 pour atteindre la salle 2, la porte 0 pour atteindre la salle 1, et la porte 3 pour atteindre la sortie. Il faut respectivement 3, 5 et 10 clés pour les ouvrir, donc 10 clés vous seront nécessaire pour pouvoir atteindre la sortie.

Pour la dernière requête, seules les portes d'identifiants compris entre 0 et 2 sont fermées (donc la porte 0 et la porte 2). Vous partez de la salle 4 et devez prendre les portes 2, 0 et 3 pour atteindre la sortie. Les portes 0 et 2 étant les seules portes fermées, vous avez besoin de respectivement 8 et 5 clés pour les ouvrir. 8 clés vous seront donc suffisantes pour atteindre la sortie.