| Fişierul intrare/ieşire: | detective.in, detective.out | Sursă | Lot Seniori Dorohoi 2019 - Baraj 2 |
| Autor | Costin Oncescu | Adăugată de |  brebenel mihnea stefan •tryharderul |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Detective
Tim Goodman si Detective Pikachu investighează sursa misteriosului gaz R care face pok emonii din Ryme City sa devina salbatici. Dupa o lunga sesiune de interogatoriu cu un Mr. Mime necooperativ, au reusit sa afle cateva informatii pretioase.
Sub Ryme City exista o retea formata din N puncte de control numerotate de la 0 la N-1, unite intre ele prin N-1 tuneluri bidirectionale, astfel incat exista un drum unic intre oricare doua puncte de control Xi si Yi (0 ≤ i ≤ M-1), Mr. Mime a mers pe cel mai scurt drum si isi aminteste concentratia minima Zi a gazului R pe care a intalnit-i in punctele de control de pe acel drum.
Ultima informatie data de Mr. Mime este ca, foarte probabil, toate mai putin doua dintre punctele de control au exact doua tuneluri adiacente.
Pentru a continue investigatie, Tim si Detective Pikachu trebuie sa afle o forma posibila a retelei de tuneluri bazata pe informatiile oferite de Mr. Mime.
Date de intrare
- linia 1: N M ,reprezentand numarul de puncte de control, respectiv numarul de informatii despre retea
- linia 2 + i (0 ≤ i ≤ M-1): Xi Yi Zi reprezentand informatiile oferite de Mr.Mime.
Fişierul de intrare detective.in ...
Date de ieşire
Fisierul de iesire va contine N-1 perechi (x,y) , reprezentând două puncte de control unite de un tunel.
Punctare
Pentru orice test punctajul maxim se obtine dacă reteaua produsă nu contrazice informatiile produse de Mr. Mime, si în plus, toate mai putin două dintre punctele de control au exact două tuneluri adiacente.
| Subtask | Punctaj | Constrangeri |
|---|---|---|
| 1 | 40 de puncte | 1 ≤ N ≤ 1000 0 ≤ M ≤ 2000 |
| 2 | 10 de puncte | 1 ≤ N &le 500 0 ≤ M ≤ 250000 Oricare ar fi 0 ≤ a,b &le N-1 exista un drum i parcurs de Mr. Mime astfel incat Xi=a si Yi=b |
| 3 | 50 de puncte | 1 ≤ N,M &le 250000 |
Exemplu
| detective.in | detective.out |
|---|---|
| 5 10 3 0 0 3 4 0 3 1 0 3 2 0 0 4 0 0 1 0 0 2 0 4 1 1 4 2 1 1 2 1 | 3 0 0 4 4 1 1 2 |
Explicaţie
O posibilă retea de tuneluri si puncte de control este reprezentată în următoarea imagine:
Următoarea retea reprezentată nu este însă corectă deoarece concentratia minimă de gaz R observată
de Mr. Mime pe drumul de la 4 la 2 este 1, dar reteaua ar indica că această concentratie este 2.
...
