Fișierul intrare/ieșire	alimentara.in, alimentara.out	Sursă	Baraj Yakuția 2015
Autor	Alexandru Văleanu	Adăugată de	Alexandru Valeanu • AlexandruValeanu
Timp de execuție pe test	0.35 sec	Limită de memorie	32768 KB
Scorul tău	N/A	Dificultate	3.5

Vezi soluțiile trimise | Statistici

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.
Cum în orice familie trebuie să existe cineva care să facă piața, Joker-ul a primit această “onoare” (cine s-ar certa cu Harley Quinn oricum?).
Astfel din când în când Joker-ul mai primește câte o listă de cumpărături, sub forma unui număr natural nenul. Cum nu vrea nici să care prea mult, nici să-și dezamăgească soția, acesta cumpără doar o parte din produse (poate chiar toate). Harley și-a dat seama destul de repede de planul său și de fiecare dată îl trimite 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 reprezentată de nodul cu numărul 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. Cum Harley Quinn este o persoană mondenă, casa celor doi se află în centrul monden al Gotham-ului (în rădăcina arborelui). Cum la noi există bănci în orice intersecție, în Gotham există câte o alimentară (în fiecare nod), cu un stoc inițial cunoscut (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 iar aceasta se întreabă care este cea mai depărtată alimentară de casă care să conține vreun aliment de pe lista sa (reprezentată de numărul l). O alimentară cu stocul s conține vreun produs de pe lista fetei dacă gcd(s, l) > 1 (cel mai mare divizor comun dintre s și l este mai mare decât 1).

Date de intrare

Fișierul de intrare alimentara.in va conține N+Q+1 linii.
Pe prima linie se vor afla 2 numere, N (numărul de intersecții ale orașului) și Q (numărul de evenimente).
Pe următoare N linii se vor afla câte 2 numere, p (părintele nodului i, 0 pentru rădăcină) și value (stocul inițial al alimentarei din nodul i).
Pe următoare Q linii se vor afla evenimentele sub forma:

• 1 X key : alimentara din nodul X capătă stocul key
• 2 key : Harley se întreabă care este distanța maximă (de la casa ei) până la o alimentară ce conține vreun aliment din lista reprezentată de key.

Date de ieșire

În fișierul de ieșire alimentara.out va conține p (p ≤ Q) linii reprezentând răspunsul la întrebările lui Harley (în ordinea în care apar în fișier).
În cazul în care nu există nicio alimentară care să respecte condițiile impuse de Harley Quinn se va afișa -1.

Restricții

• 1 ≤ $N ≤ 150.000$
• 1 ≤ $Q ≤ 300.000$
• 1 ≤ value_i, key ≤ 1.000.000, 1 ≤ i ≤ 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$
• Distanța dintre două noduri se definește ca fiind numărul de muchii dintre cele două
• Se recomandă parsarea intrării

Exemplu

alimentara.in	alimentara.out
4 3 0 4 1 3 1 6 3 11 2 35 1 3 10 2 35	-1 1

Explicații

Pentru prima întrebare nu există niciun nod care să respecte cerintă.
Pentru cea de-a doua întrebare există doar nodul 3, aflat la distanța 1 de rădăcină.

Exemplu de parser

== code(cpp) |
const int BUFFER_SIZE = (1 << 16);
char buffer[BUFFER_SIZE];
int position = BUFFER_SIZE;

char getChar(FILE *in)
{ if ( position == BUFFER_SIZE ) { position = 0; fread(buffer, BUFFER_SIZE, 1, in); }

return buffer[position++]; }

int getInt(FILE *in)
{ int a = 0; char ch; int sgn = 1;

do { ch = getChar(in); } while ( !isdigit(ch) && ch != ‘-’ ); if ( ch == ‘-’ ) { sgn = -1; ch = getChar(in); } do { a = (a << 3) + (a << 1) + ch – ‘0’; ch = getChar(in); } while ( isdigit(ch) ); return a * sgn; } ==