Fişierul intrare/ieşire:alimentara.in, alimentara.outSursăBaraj Yakuția 2015
AutorAlexandru ValeanuAdăugată deAlexandruValeanuAlexandru Valeanu AlexandruValeanu
Timp execuţie pe test1.1 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Alimentară

The Joker: Why so serious?
Joker flicks his wrist and Gambol goes down.

După confruntarea finală dintre Suicide Squad şi Batman, pierdută de cel din urmă, Joker şi Harley Quinn s-au căsătorit şi trăiesc fericiţi în ceea ce a mai rămas din Gotham.

În orice familie cineva face piaţa, iar Joker-ul a primit această onoare (cine s-ar certa cu Harley Quinn oricum?). Astfel, ocazional, Joker-ul primeşte câte o listă de cumpărături, sub forma unui număr natural nenul. Deoarece Joker-ul a făcut burtică, Harley îl trimite mereu până la cea mai depărtată alimentară.

Gotham este un oraş modern, organizat sub forma unui arbore (graf conex aciclic) cu rădăcină (rădăcina este nodul 1). Nodurile reprezintă intersecţiile şi sunt conectate între ele prin străzi bidirecţionale, astfel încât din orice intersecţie se poate ajunge în oricare alta. Toate străzile au lungime 1. Casa celor doi se află în nodul 1 (centrul monden al Gotham-ului). În Gotham există câte o alimentară în fiecare nod k, cu un stoc iniţial Sk (un număr natural nenul).

În Gotham se pot întâmpla două tipuri de evenimente:

  • Se modifică stocul unei alimentare.
  • Harley îl trimite la cumpărături pe Joker cu o listă de cumpărături L. Ea se întreabă care este cea mai depărtată alimentară de casă care să corespundă listei. O alimentară cu stocul S corespunde listei dacă cmmdc(S, L) > 1.

Date de intrare

Fişierul de intrare alimentara.in va conţine N + Q + 1 linii.
Pe prima linie se vor afla numerele N (numărul de intersecţii ale oraşului) şi Q (numărul de evenimente).
Pe următoarele N linii se vor afla perechi de numere Pk Sk. Ele reprezintă părintele nodului k şi respectiv stocul alimentarei k. Prin convenţie, P1 este 0.
Pe următoarele Q linii se vor afla evenimentele sub forma:

  • 1 X S : alimentara din nodul X capătă stocul S
  • 2 L : Harley se întreabă care este distanţa maximă (de la casa ei) până la o alimentară ce corespunde listei de cumpărături L.

Date de ieşire

Fişierul de ieşire alimentara.out va conţine maxim Q linii reprezentând răspunsurile la întrebările lui Harley (în ordinea în care apar în fişier).

În cazul în care pentru o listă L nu există nicio alimentară care să corespundă se va afişa -1.

Restricţii

  • 1 ≤ N ≤ 150.000
  • 1 ≤ Q ≤ 300.000
  • 1 ≤ Sk, S, L ≤ 1.000.000, 1 ≤ k ≤ N
  • Pentru 20% din punctaj se garantează că N, Q ≤ 1.000
  • Pentru 40% din punctaj se garantează că N, Q ≤ 50.000
  • Pentru 60% din punctaj se garantează că N, Q ≤ 100.000
  • Se recomandă parsarea intrării

Exemplu

alimentara.inalimentara.outimagine
7 3
0 1
1 4
1 7
5 3
3 8
3 3
3 5
2 2
1 3 10
2 7
2
-1
alimentara.inalimentara.outimagine
5 5
0 3
3 1
1 2
3 10
1 6
2 20
1 4 7
2 40
2 991
2 35
2
1
-1
2

Explicaţii pentru primul exemplu

Pentru prima întrebare există 2 alimentare posibile: 2, 5. Cea din nodul 5 este cea mai depărtată.
Pentru cea de-a doua întrebare nu există nicio alimentară.

Explicaţii pentru cel de-al doilea exemplu

Pentru prima întrebare există 3 alimentare posibile: 3, 4, 5. Cea din nodul 4 este cea mai depărtată.
Pentru a doua întrebare există 2 alimentare posibile: 3, 5. Amândouă sunt situate la aceeaşi distanţă.
Pentru a treia întrebare nu există nicio alimentară.
Pentru a patra întrebare există o singură alimentară posibilă, în nodul 4.

Trebuie sa te autentifici pentru a trimite solutii. Click aici