Prologin, the French National Computer Science Contest

Énoncé¶

Enfin sorti de la salle précédente, vous passez par un sas avant d'accéder à la prochaine épreuve. Cependant, vous vous rendez compte que la porte permettant d'accéder à la prochaine salle, supposée ouverte, est cassée !

Il va donc falloir trouver un moyen de l'ouvrir.

Vous étudiez le système des portes en observant la porte d'entrée que vous venez d'emprunter et comprenez très vite le principe : Un réseau de puces est positionné sur chaque porte, chaque puce étant reliée aux autres par des fils. Si les puces ne sont pas toutes connectées entre elles, il est impossible d'ouvrir une porte : le graphe formé doit être connexe pour pouvoir espérer ouvrir la porte. Une fois que le graphe est connexe, le mécanisme d'ouverture active la puce centrale du graphe, ce qui déclenche l'ouverture de la porte. Une puce est dite centrale si la suppression de celle-ci dans un graphe connexe de $N$ puces entraîne une décomposition de ce graphe en plusieurs composantes connexes d'au plus $\lceil N/2 \rceil$ puces chacune.

Vous analysez donc à présent la porte de sortie supposée être ouverte, et vous constatez que le réseau de puces n'est pas endommagé : le réseau forme un arbre, chaque puce est reliée au réseau, la porte est censée pouvoir s'ouvrir. Cependant, c'est le mécanisme d'activation qui ne fonctionne plus ! La puce centrale n'est plus reliée au bouton d'ouverture de la porte. Heureusement, vous avez tout juste moyen d'insérer un câble pour pouvoir connecter une puce au bouton. Mais malheureusement, vous n'avez pas de câble sur vous !

C'est alors qu'il vous vient une idée : Vous allez devoir minutieusement retirer certains fils de la porte d'entrée, en prenant bien garde à ne jamais bloquer la porte, cela pourrait déclencher un système d'alarme ! Vous pouvez retirer un fil sans déclencher l'alarme que si le réseau de puce reste connexe après la suppression du fil, et que chaque puce centrale reste centrale après la suppression de ce fil. Vous allez ensuite pouvoir mettre bout à bout chaque fil retiré pour former un plus long câble, d'une longueur égale à la somme des longueurs de chaque fil. Vous allez tenter d'insérer ce câble, si possible, afin de relier une puce centrale de la porte de sortie au bouton de déclenchement. Attention, chaque puce se situe à une distance précise du bouton, et certaines puces peuvent ne pas être atteignables si elles sont trop loin du bouton pour être reliées par votre câble ! Si vous avez réussi à connecter une puce centrale de la porte de sortie au bouton, vous devriez pouvoir ouvrir la porte et passer à l'épreuve suivante !

Entrée¶

L’entrée contiendra :

Sur la première ligne, un entier : pucesEntree, le nombre de puces présentes sur la porte d'entrée.
Sur la ligne suivante, un entier : filsEntree, le nombre de fils présents sur la porte d'entrée.
Sur les lignes suivantes, une liste de filsEntree éléments : entree, liste des fils présents sur la porte d'entrée.
- Une ligne par élément de la liste : séparés par des espaces, un entier puceEntree1 (première extrémité du fil), un entier puceEntree2 (seconde extrémité du fil), et un entier longueur (longueur du fil).
Sur la ligne suivante, un entier : pucesSortie, le nombre de puces présentes sur la porte de sortie.
Sur la ligne suivante, un entier : filsSortie, le nombre de fils présents sur la porte de sortie.
Sur les lignes suivantes, une liste de filsSortie éléments : sortie, liste des fils présents sur la porte de sortie.
- Une ligne par élément de la liste : séparés par des espaces, un entier puceSortie1 (première extrémité du fil), et un entier puceSortie2 (seconde extrémité du fil).
Sur la ligne suivante, une liste de pucesSortie entiers séparés par des espaces : distance, distance entre le bouton et chaque puce présente sur la porte de sortie.

Sortie¶

S'il est possible d'ouvrir la porte, afficher l'index de la puce (indexé à 0) qui permet d'ouvrir la porte. Sinon, afficher "-1".

Contraintes¶

$2 \le pucesEntree \le 1\,000$
$1 \le filsEntree \le 2\,000$
$2 \le pucesSortie \le 1\,000$
$1 \le filsSortie \le 999$
$0 \le distance[ ] \le 1\,000\,000\,000$
$0 \le longueur \le 100\,000$
Il est garanti que le réseau situé sur la porte d'entrée est connexe.
Il est garanti que le réseau situé sur la porte de sortie forme un arbre.
Il est garanti que le réseau situé sur chaque porte possède au moins une puce centrale.
Il est garanti qu'il n'existe jamais plus d'une solution valide.

Contraintes de performance¶

$2 \le pucesEntree \le 100\,000$
$1 \le filsEntree \le 200\,000$
$2 \le pucesSortie \le 100\,000$
$1 \le filsSortie \le 99\,999$

Runtime constraints

Maximum memory usage: 100000 kilobytes
Maximum execution time: 1000 milliseconds

Input/output samples

Sample input

7
9
0 1 5
0 2 8
0 3 6
1 2 7
2 3 4
2 4 5
2 5 2
4 5 4
4 6 9
6
5
0 2
1 2
2 3
3 4
4 5
18 28 20 32 24 15

Sample output

Note

Voici une possible représentation de la porte d'entrée :

Porte d'entrée

La puce numérotée 2 est une puce centrale de la porte. En effet, sa suppression diviserait le graphe en deux composantes connexes : la première, sur le battant de gauche, contenant 3 puces : les puces numérotées 0, 1 et 3; la deuxième, sur le battant de droite, contenant également 3 puces : les puces numérotées 4, 5 et 6. La taille de chacune de ces composantes est inférieure ou égale à la moitié de la taille du graphe original, la puce est bel et bien une puce centrale. Il a donc été possible d'ouvrir cette porte en activant la puce numérotée 2.

Maintenant, il est possible de subtiliser le fil reliant les puces 0 et 2, le fil reliant les puces 1 et 2 ainsi que le fil reliant les puces 2 et 4 (représentés en rouge) tout en respectant toujours toutes les conditions : le graphe reste connexe, et l'unique puce centrale du graphe est toujours une puce centrale (la puce numérotée 2 reste centrale après la suppression de ces trois fils). En enlevant ces trois fils, vous pouvez former un câble d'une longueur totale de 8 + 7 + 5 = 20 unités sans enclencher le système d'alarme.

Ensuite, la porte de sortie peut ressembler à cela :

Porte de sortie

La puce numérotée 2 est une puce centrale de cette porte. En effet, sa suppression diviserait l'arbre en trois sous-arbres, de taille 1, 1, et 3. La taille de l'arbre original étant de 6, la puce 2 est une puce centrale valide. De plus, la dernière ligne de l'entrée indique que la puce numérotée 2 (donc représentée par le 3e nombre de cette liste) se situe à une distance de 20 unités du bouton d'activation. Nous avons donc tout juste de quoi activer la puce 2 pour ouvrir la porte !

Notez que la puce numérotée 3 est également une puce centrale, mais que sa distance ne permet pas son activation.

Sample input

Sample output

-1

Note

Il est dans ce cas impossible de subtiliser un fil de la porte d'entrée sans déclencher le système d'alarme. En effet, le réseau d'entrée forme un arbre, et la suppression d'une quelconque arête de l'arbre ne le rendrait plus connexe.

Le réseau présent sur la porte de sortie est similaire au réseau présent sur la porte d'entrée. La puce 4 est la seule puce centrale du réseau, et son activation est impossible au vu de sa distance, certes de 1 unité seulement, mais toujours supérieure à la longueur de câble en notre possession : 0.

Submit your solution

You have to register or log in to be able to submit your solution.

Porte centrée – Regional event 2022