Bataille par élimination – Regional event 2020

Level 6

Énoncé

Les forces de l'empire se sont réparties sur une planète à la topologie un peu complexe. Les pentes de certaines montagnes sont tellement raides qu'on ne peut que les descendre ! L'empire a déployé l'ensemble de ses soldats en petites troupes partout sur la planète. Cependant la rébellion possède sur cette planète un puissant dispositif de souterrains (complètement indétectables par les troupes ennemies) qui lui permet de se déplacer très vite d'une montagne à une autre.

La rébellion prépare son plan d'attaque et anticipe ainsi la réaction des troupes ennemies : si une troupe est attaquée à un point donné, toutes les troupes en mesure de les rejoindre arrivent instantanément leur venir en aide.

Toutefois, les rebelles ne pourront gagner la bataille que s'ils sont strictement plus nombreux que les soldats de l'empire. En revanche, s'ils gagnent, ils restent tous vivants et peuvent tous aller attaquer autre part.

Ils souhaitent donc comprendre quels points il faut attaquer en premier et en déduire le nombre minimum de rebelles nécessaires pour neutraliser l'ensemble des troupes de l'empire.

Entrée

L'entrée contiendra :

  • Sur la première ligne, un entier : $N$, le nombre de troupes de soldats de l'empire.
  • Sur la ligne suivante, une liste de $N$ entiers séparés par des espaces : $S_i$, le nombre de soldats de la troupe.
  • Sur la ligne suivante, un entier : $M$, le nombre de chemins (dirigés) possibles d'une troupe à une autre.
  • Sur les lignes suivantes, une liste de $M$ éléments : $chemins$, la liste des chemins possibles.
    • Une ligne par élément de la liste : séparés par des espaces, un entier $a_j$ (la première troupe qui peut rejoindre la deuxième), et un entier $b_j$ (la troupe qui peut être rejointe).

Sortie

Affichez le nombre minimal de rebelles pour vaincre à toutes les batailles.

Contraintes

  • $ 1 \leq N \leq 50000 $
  • $ 1 \leq S_i \leq 100 $
  • $ 1 \leq M \leq 70000 $
  • $ 1 \leq a_j \leq N $
  • $ 1 \leq b_j \leq N $

Runtime constraints

Maximum memory usage
5000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
2
5 3
1
2 1
Sample output
6
Note

Bonne statégie : Attaquer la troupe 2 qui a 3 soldats d’abord (la troupe 1 ne peut pas venir l’aider) puis la troupe 1 avec 5 soldats qui peut donc être neutralisé avec 6 rebelles. Mauvaise stratégie : Attaquer 1 en premier, les soldats de la troupe 2 arrivent instantanément, il y a 8 soldats, il faut 9 rebelles pour les battres.

Sample input
4
3 2 1 1
4
1 2
2 4
4 3
3 2
Sample output
5
Note

On attaque 1 en premier, puis on peut attaquer au hasard entre 2, 3 et 4, car si l'un est attaqué, les autres viendront à l'aide imédiatement. Il y aura donc 4 soldats et donc il faut 5 rebelles pour gagner.

Submit your solution

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