== include(page="template/taskheader" task_id="cangrena") ==
Poveste şi cerinţă...
!{width: 300px; float: right; margin: 10px}problema/cangrena?main.png!
Oraşul TownsVille este un oraş foarte aglomerat. Acesta este format din $N$ intersecţii numerotate de la $1$ la $N$, conectate prin $M$ străzi. Primarul oraşului cunoaşte pentru câteva din cele $N$ intersecţii un coeficient pozitiv $A[i]$ reprezentând aglomeraţia din intersecţia $i$. Pentru intersecţiile în care acest coeficient este necunoscut, primarul este obligat să fixeze personal acest coeficient (de asemenea pozitiv).
Iniţial, primarului nu prea îi păsa ce coeficienţi selectează. Dacă pentru o intersecţie coeficientul era prea mic, lumea ar fi fost mulţumită, dacă nu, ar fi impus taxe, deci el ar fi fost mulţumit. Din păcate, Gaşca Cangrenă este pusă pe tot felul de mârlănii: de la aruncat hârtie în coşul cu plastic, până la furat îngheţata copiilor mici, orice e posibil. Astăzi, în schimb, aceştia s-au decis să fure cauciucurile maşinilor din interiorul intersecţiilor. Astfel, primarul şi-a impus următoarea regulă: pentru oricare două intersecţii conectate printr-o stradă, diferenţa coeficientului de aglomeraţie între cele două intersecţii trebuie să nu fie prea mare. Dacă această diferenţă ar fi mult prea mare, Gaşca Cangrenă ar ataca cu siguranţă intersecţia mai aglomerată. Altfel, aceştia ar fi confuzi pe care să o atace (întrucât nu ştiu să numere câte maşini sunt într-o intersecţie), fapt care le-ar câştiga timp fetiţelor Powerpuff să vină să salveze situaţia.
Dându-se configuraţia oraşului TownsVille, precum şi coeficienţii cunoscuţi de aglomeraţie ai unor intersecţii, scopul vostru este să selectaţi câte un coeficient de aglomeraţie pentru restul intersecţiilor astfel încât să minimizaţi diferenţa maximă între oricare două intersecţii conectate printr-o stradă.
h2. Date de intrare
Fişierul de intrare $cangrena.in$ ...
Fişierul de intrare $cangrena.in$ va conţine pe prima linie două numere naturale $N$ şi $M$, cu semnificaţia din enunţ. Pe următoarea linie se vor afla $N$ numere, al $i$-lea număr reprezentând coeficientul de aglomeraţie al intersecţiei numerotate cu indicele $i$, dacă acest coeficient este cunoscut, $-1$ altfel. Următoarele $M$ linii vor conţine câte două numere naturale $A$ şi $B$, reprezentând faptul că intersecţia $A$ este conectată cu intersecţia $B$ printr-o stradă.
h2. Date de ieşire
În fişierul de ieşire $cangrena.out$ ...
În fişierul de ieşire $cangrena.out$ va conţine o singură linie cu $N$ numere naturale pozitive (separate prin cate un spaţiu), al i-lea număr reprezentând coeficientul de aglomeraţie al intersecţiei cu indicele i (se vor afişa inclusiv coeficienţii fixaţi iniţial).
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 200.000$
* din orice intersecţie se poate ajunge în oricare alta prin drumurile existente
* există cel puţin o intersecţie cu coeficientul de aglomeraţie cunoscut
* în orice intersecţie ajunge cel puţin o stradă
* străzile sunt bidirecţionale
* coeficienţii de aglomerare *cunoscuţi* sunt numere naturale nenule mai mici sau egale cu $1.000.000.000$
h2. Exemplu
table(example). |_. cangrena.in |_. cangrena.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
table(example). |_. cangrena.in |_. cangrena.out |_. explicaţie |
| 4 3
10 -1 20 12
1 2
2 3
4 2
| 10 15 20 12
| !problema/cangrena?explicatie1.png!
|
| 8 8
-1 33 -1 -1 -1 -1 -1 31
1 3
1 6
2 5
3 8
4 8
5 6
5 7
6 7
| 33 33 32 32 34 34 35 31
| !problema/cangrena?explicatie2.png!
|
...
== include(page="template/taskfooter" task_id="cangrena") ==
