Fişierul intrare/ieşire:flareon.in, flareon.outSursăLot Seniori Alexandria, 2017, baraj 6
AutorAdrian BudauAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test3 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Flareon

Oraşul Alexandria a fost luat cu asalt de grupuri de durants, pokemoni furnică! Aceştia şi-au construit N muşuroaie numerotate de la 1 la N, conectate între ele prin N-1 tuneluri bidirecţionale, astfel încât să se poată ajunge dintr-un muşuroi în oricare altul urmând tunelurile. Definim distanţa d(i,j) ca fiind egală cu numărul minim de tuneluri care trebuie traversate pentru a ajunge din muşuroiul i în muşuroiul j.
Candela, liderul echipei Valor, a convocat M flareoni, al i-lea dintre aceştia fiind staţionat lângă muşuroiul Pos[i] şi având o mişcare Lava Plume de putere Power[i]. Un atac de tip Lava Plume de putere p efectuat la muşuroiul i, adaugă la gradul de distrugere Dmg[j] al muşuroiului j valoarea max(0, p - d(i, j)).
Se cere să se determine, pentru fiecare muşuroi i, gradul de distrugere Dmg[i] al acestuia după atacurile tuturor celor M flareoni.

Date de intrare

Fişierul de intrare flareon.in va conţine, pe primul rând, pe N şi M.
Pe al doilea rând vor apărea N-1 numere. Considerăm că există un tunel între muşuroiul i+1 şi cel cu indicele egal cu cel de-al i-lea număr.
Urmează M rânduri. Pe fiecare rând va apărea o pereche X P ce reprezintă că există un flareon la muşuroiul X cu puterea P.

Date de ieşire

Fişierul de ieşire flareon.out va conţine elementele şirului Dmg, fiecare pe câte un rând.

Restricţii şi precizări

  • 1 ≤ N ≤ 200.000
  • 1 ≤ M ≤ 500.000
  • 1 ≤ P ≤ 1.000.000.000
  • 1 ≤ X ≤ N
  • Pentru 20% din teste, N ≤ 1.000 şi M ≤ 2.000
  • Pentru 70% din teste, N ≤ 30.000 şi M ≤ 30.000
  • Lângă un muşuroi se pot afla mai mulţi flareoni.

Exemplu

flareon.inflareon.out
4 3
1 1 3
2 2
3 2
4 10
10
9
11
11
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?