Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2018-03-25 16:28:10.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:restrict.in, restrict.outSursăGrigore Moisil 2018, 11-12
AutorTudor CozmaAdăugată degrigore.moisilGrigore Moisil grigore.moisil
Timp execuţie pe test0.35 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Restrict

Se dă un arbore cu N noduri numerotate de la 1 la N cu rădăcina în nodul 1. Fiecare muchie are asociat un cost. Pentru a ajunge din nodul 1 într-un nod D, se izolează lanţul dintre nodul 1 şi nodul D de restul arborelui, apoi se parcurg pe acest lanţ pornind din nodul 1 muchii în jos sau în sus, respectând restricţiile puse pe noduri, până când se ajunge în nodul D. Definim o restricţie pusă pe un nod X ca fiind un alt nod Y, care este strămoş al nodului X, cu semnificaţia că nu putem intra în nodul X dacă nodul Y se află printre ultimele K noduri vizitate. La fiecare trecere printr-o muchie, se adaugă la costul parcurgerii costul asociat acelei muchii.
Să se afle pentru fiecare nod i, 1 ≤ i ≤ N, în parte, care este costul minim de a ajunge din nodul 1 în nodul i, respectând restricţiile puse pe noduri.

Date de intrare

Fişierul de intrare restrict.in conţine pe prima linie două numere întregi N şi K, cu semnificaţia din enunţ. Următoarele N-1 linii conţin câte 3 numere întregi fiecare. A i-a linie dintre aceste N-1 linii conţine următoarele 3 valori: primul număr reprezintă părintele nodului i+1, al doilea număr reprezintă costul muchiei dintre nodul i+1 şi părintele acestuia, al treilea număr reprezintă restricţia pusă pe nodul i+1, această valoare este egală cu -1 dacă pe nodul i+1 nu este pusă nicio restricţie.

Date de ieşire

Fişierul de ieşire restrict.out trebuie să conţină N linii, fiecare conţinând o singură valoare, a i-a valoare reprezentând costul minim de a ajunge din rădăcină în nodul i sau -1 în cazul în care nu se poate ajunge în acest nod.

Restricţii

  • 0 ≤ N, K ≤ 100 000
  • 0 ≤ costul unei muchii ≤ 1 000 000
  • Pentru teste în valoare de 10 puncte, se garantează că 1 ≤ N ≤ 1 000, arborele este un lanţ (fiecare nod are cel mult un fiu) şi restricţiile nu se intersectează (dacă restricţia pusă pe nodul X este nodul Y, atunci toate nodurile dintre X şi Y sunt fără restricţii).
  • Pentru alte teste în valoare de 30 puncte, se garantează că 1 ≤ N ≤ 1 000.
  • Problema va fi evaluată pe teste în valoare de 90 de puncte.
  • Exemplele vor reprezenta teste în valoare de 10 puncte "din oficiu".

Exemplu

restrict.inrestrict.out
6 3
3 2 -1
1 1 -1
1 8 -1
2 3 1
1 4 1
0
3
1
8
10
-1
14 6
10 20 -1
7 1 5
10 2 1
1 7 -1
9 7 11
8 0 -1
4 7 13
2 11 -1
11 3 -1
13 10 -1
3 100 -1
5 4 -1
2 165 2
0
44
44
32
7
106
43
43
55
24
21
144
11
-1

Explicaţie

Pentru primul exemplu avem arborele:

Pentru a ajunge din rădăcină în nodul 1 se observă că nu trebuie să facem nicio mutare, deci costul minim este 0.
Pentru a ajunge din rădăcină în nodul 2 cu un cost minim vom parcurge următorul traseu: 1 -> 3 -> 2, costul fiind 1 + 2 = 3.
Pentru a ajunge din rădăcină în nodul 3 cu un cost minim vom parcurge următorul traseu: 1 -> 3, costul fiind 1.
Pentru a ajunge din rădăcină în nodul 4 cu un cost minim vom parcurge următorul traseu: 1 -> 4, costul fiind 8.
Pentru a ajunge din rădăcină în nodul 5 cu un cost minim vom parcurge următorul traseu: 1 -> 3 -> 2 -> 3 -> 2 -> 5, costul fiind 1 + 2 + 2 + 2 + 3 = 10. Restricţia pusă asupra nodului 5 nu ne lasă să intrăm în acest nod dacă nodul 1 se află printre ultimele 3 noduri vizitate. De aceea, din nodul 2 mergem înapoi în nodul 3 şi apoi coborâm până în nodul 5. Astfel, ultimele 3 noduri prin care trecem înainte de a intra în nodul 5 sunt 2, 3, 2.
Nu se poate ajunge din rădăcină în nodul 6, deoarece restricţia pusă pe nodul 6 nu ne lasă să intrăm în acest nod dacă nodul 1 se află printre ultimele 3 noduri vizitate. Costul minim pentru acest nod este -1.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?