Prologin
2024
Énoncé¶
Les tensions entre tous les dieux éclatent. Jøsëf Marchand s'est montré trop gentil et a aidé beaucoup de dieux. Ainsi, les dieux ont une dent contre lui pour avoir aidé leurs ennemis et veulent en finir avec lui. Jøsëf ne peut plus compter que sur votre aide pour s'en sortir en un seul morceau.
L'endroit où Jøsëf se situe est représenté par un graphe
$G$ = (aretes, [1, nombre sommets]).
Un sous-ensemble des sommets de $G$ sont des mines posées par les dieux.
Ces mines ne sont pas comme les mines traditionnelles car elles peuvent détecter Jøsëf de très loin. S'il se fait détecter, c'est le drame : la mine le conduira à une mort certaine.
Jøsëf Marchand doit se déplacer $R$ fois.
Vous devez l'aider en lui indiquant s'il est possible d'aller du sommet depart
au sommet arrivee sans jamais passer sur une case d'une distance ≤ distance
d'un sommet miné.
depart, arrivee, distance peuvent changer parmi les $R$ déplacements.
On considère qu'une case $A$ est à une distance $d$ d'une case $B$ quand $d$ est le nombre d'arêtes du plus court chemin entre $A$ et $B$.
Si les deux sommets d'une requête se sont pas dans la même composante connexe,
vous devez afficher non.
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : nombre sommets, le nombre de sommets.
- Sur la ligne suivante, un entier : nombre trous, le nombre de trous.
- Sur la ligne suivante, une liste de nombre trous entiers séparés par des espaces : trous, les numéros de chaque sommet ayant une mine.
- Sur la ligne suivante, un entier : nombre aretes, le nombre d'arêtes.
- Sur les lignes suivantes, une liste de nombre aretes éléments :
aretes, les arêtes (non orientées) entre chaque sommet.
- Une ligne par élément de la liste : séparés par des espaces, un entier u (premier sommet), et un entier v (deuxième sommet).
- Sur la ligne suivante, un entier : nombre requetes, le nombre de requêtes.
- Sur les lignes suivantes, une liste de nombre requetes éléments :
requetes, chaque requête.
- Une ligne par élément de la liste : séparés par des espaces, un entier portee (portee des mines), un entier depart (sommet de départ), et un entier arrivee (sommet d'arrivée).
Sortie¶
Pour chaque requête, afficher sur une ligne oui s'il est possible pour Jøsëf
de se déplacer entre les deux sommets de manière sûre, non sinon.
Contraintes¶
- $1 \le \text{nombre sommets} \le 1\,000$
- $1 \le \text{nombre aretes} \le 10\,000$
- $1 \le \text{nombre requetes} \le 1\,000$
- $1 \le \text{nombre trous} \le \text{nombre sommets}$
- $1 \le \text{trous[i]} \le \text{nombre sommets}$
- $0 \le \text{portee} \le \text{nombre sommets}$
- $1 \le \text{depart}, \text{arrivee} \le \text{nombre sommets}$
- $1 \le u, v \le \text{nombre sommets}$
- $\text{depart} \neq \text{arrivee}$
Contraintes de performance¶
- $1 \le \text{nombre sommets} \le 100\,000$
- $1 \le \text{nombre aretes} \le 100\,000$
- $1 \le \text{nombre requetes} \le 100\,000$
