Fişierul intrare/ieşire:funnygraph.in, funnygraph.outSursăIIOT 2019-20 Runda 1
AutorTulba-Lecu GabrielAdăugată deunibucPoli2019Comisia IIOT 2019-20 unibucPoli2019
Timp execuţie pe test3 secLimită de memorie512000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Funnygraph

Ţara Bugland este formată din N oraşe. Fiind o ţară nouă, cele N oraşe nu sunt unite de niciun drum, astfel, guvernul a decis să pornească un proiect care va dura exact M zile şi care are ca scop crearea unei reţele de drumuri între cele N oraşe.

În fiecare zi a proiectului muncitorii din Bugland construiesc două drumuri noi unidirecţionale, un drum de la oraşul x la oraşul y cu cost z şi un alt drum de la oraşul y la oraşul x cu cost -z.

După fiecare zi, locuitorii din Bugland îşi pun următoarea întrebare: există o modalitate de a numerota oraşele astfel încât dacă există o muchie de la oraşul x la oraşul y, costul muchiei să fie Cx-Cy, unde Ci este numărul atribuit oraşului i?

Date de intrare

Din funnygraph.in se vor citi de pe prima linie două numere N şi M, numărul de oraşe respectiv durata proiectului.
Pe următoarele M linii se găsesc câte trei numere x, y, z reprezentând drumurile construite în fiecare zi.

Date de ieşire

În funnygraph.in se vor găsi M linii, pe linia i fiind YEP :) dacă există o modalitate de a numerota oraşele, sau NOPE :/ în caz contrar.

Restricţii

  • 1 \leq N \leq 5 \cdot 10^4
  • 1 \leq M \leq 10^5
  • -10^9 \leq z_i \leq 10^9\ \forall\ 1 \leq i \leq M
  • 0 \leq x_i, y_i \leq N - 1\ \forall\ 1 \leq i \leq M
  • Pentru teste in valoare de 30 de puncte, 1 \leq N \leq 10^3$ ; $1 \leq M \leq 10^4
  • Bugland poate avea drumuri multiple între două oraşe sau chiar drumuri de la un oraş la el însuşi.

Exemplu

funnygraph.infunnygraph.out
4 5
0 1 1
1 3 -1
3 0 0
3 2 4
2 0 3
YEP :)
YEP :)
YEP :)
YEP :)
NOPE :/
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?