Fişierul intrare/ieşire:ciob.in, ciob.outSursăad-hoc
AutorAndrei Poenaru, Mihai-Alexandru DusmanuAdăugată dedushmiMihai-Alexandru Dusmanu dushmi
Timp execuţie pe test0.05 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ciob

Undeva, departe, exista o tara a carei retea stradala are structura unui graf conex aciclic, orasele fiind reprezentate de noduri, iar strazile de muchii. Ministrul responsabil cu salubritatea din fiecare oras tocmai a aflat ca Ciob cel Mic si Rau va veni in inspectie. El va ateriza cu elicopterul intr-un oras si va parcurge un drum simplu (un drum pe parcursul caruia nu va vizita acelasi oras de mai multe ori). Ministrul nostru a reusit sa afle traseele posibile. Pentru un traseu se cunosc urmatoarele: orasul in care aterizeaza Ciob si 2 liste de orase. Prima lista contine orasele din care Ciob ar trebui sa poata decola spre casa, iar a doua lista contine orasele din care Ciob nu ar trebui sa poata decola. Fiecare oras din tara are un grad de curatenie, iar gradul de multumire al lui Ciob la un moment dat este suma gradelor de curatenie a oraselor prin care a trecut. Orasele din cele 2 liste au asociat un grad de libertate (daca un oras face parte din 2 trasee distincte atunci el poate avea, in cele 2 situatii, grade de libertate diferite). Se considera ca Ciob poate decola dintr-un oras daca gradul sau de multumire in momentul in care il tranziteaza este mai mare sau egal cu gradul de libertate al orasului. De asemenea, marele sef nu poate decola daca gradul sau de multumire in momentul in care il viziteaza este strict mai mic decat gradul de libertate al orasului,.

Ministrul va cere sa ii spuneti ce grad de curatenie ar trebui sa aiba fiecare oras pentru a fi respectate toate restrictiile. Gradele de curatenie pot fi si negative( ministrul manuieste exceptional ranga si tomberonul). Pentru a va ajuta el va mai dezvaluie 2 proprietati ale traseelor posibile:
* daca 2 trasee se intersecteaza, atunci unul este inclus in celalalt
* daca x si y sunt cele mai apropiate 2 puncte ale traseelor [a, b] si [c, d], atunci x apartine multimii {a, b} si y apartine multimii {c, d}( prin notatia [a, b] intelegem traseul care incepe in orasul a, iar ultimul sau nod parcurs este orasul b)

Date de intrare

Pe prima linie a fisierului ciob.in se afla numarul N, nr de orase. Pe urmatoarele N - 1 linii se afla 2 numere, x y, cu semnificatia ca exista o sosea intre orasele x si y. Pe linia N + 1 se alfa numarul M, numarul de trasee. Pe fiecare dintre urmatoarele 3 * M linii sunt descrise traseele posibile. Pe linia N + 3 * i - 1 se afla nodul de plecare. Pe linia N + 3 * i se afla lista oraselor de pe traseul i din care Ciob poate pleca. Pe linia N + 3 * i + 1 se afla lista oraselor de pe traseul i din care Ciob nu poate pleca. Randurile care descriu o lista contin un numar k, numarul de orase din acea lista, urmat de k perechi de numere o g, o = orasul, iar g = gradul sau de libertate.

Date de ieşire

În fişierul de ieşire ciob.out se vor afisa N numere reprezentand gradele de curatenie ale oraselor, al i-lea numar fiind gradul de curatenie al orasului i. Daca exista mai multe solutii se poate afisa oricare atat timp cat numerele sunt in intervalul [- 2 * 109, 2 * 109].

Restricţii

  • 1 ≤ N ≤ 10000
  • 0 ≤ M ≤ numarul maxim de trasee posibile
  • Nu este neaparat ca Ciob sa poata pleca din orasul in care aterizeaza.
  • Se garanteaza ca exista solutie pentru datele de test.
  • Se garanteaza ca nu vor exista 2 drumuri identice( ca noduri) in fisierul de intrare.
  • Ciob decoleaza dintr-un oras dupa ce il tranziteaza.

Exemplu

ciob.inciob.out
10
1 10
10 3
1 7
10 2
2 9
9 8
1 4
2 6
1 5
3
2
3 2 12 1 -41 7 -102
1 10 150
2
1 1 -70
2 2 35 10 126
2
1 10 42
1 2 109
0 34 0 0 0 8 0 0 8 8 0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content