Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | sistem3.in, sistem3.out | Sursă | Algoritmiada 2014, Runda 1 |
| Autor | Adrian Vladu | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sistem3
Se da un graf neorientat si conex G ce are N noduri si N muchii. Acest graf are asociat fiecarui nod o valoare numita potential. Astfel potentialul nodului i este p[i]. Deasemenea fiecare muchie are asociata si ea un cost w (nu unic).
Definim gradientul unui nod i suma (p[j] - p[i]) * w[j][i] modulo M (M dat) unde j este un vecin de-al lui i, iar w[j][i] este costul muchiei dintre i si j.
Din pacate potentialele nodurilor au fost pierdute insa se cunosc gradientele si costurile de pe muchii. Vi se cere sa reconstituiti potentialele nodurilor stiind ca ele aveau valori cuprinse intre 0 si M - 1.
Date de intrare
Fişierul de intrare sistem3.in va contine pe prima linie doua numere naturale N si M reprezentand numarul de noduri (si muchii) din graf, respectiv valoarea fata de care se face modulo.
Urmatoarele N randuri vor contine fiecare 3 numere naturale x, y si w cu semnificatia: exista o muchie intre nodul x si nodul y de cost w.
Urmatoarea si ultima linie va contine N numere naturale, a i-a valoare reprezentand gradientul nodului i.
Date de ieşire
În fişierul de ieşire sistem3.out trebuie sa se gaseasca N linii fiecare continand o valoare naturala intre 0 si M - 1, acestea reprezentand in ordine potentialele nodurilor 1, 2, .., N.
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ x, y ≤ N
- 1 ≤ w ≤ M - 1
- 2 ≤ M ≤ 46000
- M e prim
- 0 ≤ gradientul oricarui nod ≤ M - 1
- Pentru 30% din teste N <= 100
- Pentru 50% din teste una din muchii este de forma x x w
Exemplu
| sistem3.in | sistem3.out |
|---|---|
| 4 2 4 2 1 2 2 1 1 4 1 1 3 1 1 0 1 0 | 0 0 1 0 |
| 5 5 2 4 4 3 5 4 3 1 3 4 1 4 1 5 4 4 1 2 2 1 | 0 4 4 3 0 |
