== include(page="template/taskheader" task_id="alimentara") ==
**Why so serios?**
**The Joker: _Why so serious?_**
[_Joker flicks his wrist and Gambol goes down._]
!>problema/alimentara?rsz_user21462_pic28746_1368451004.jpg!
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 "centrul" orașului și 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 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 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 $S[~k~]$ (un număr natural nenul).
În Gotham se pot întâmpla două tipuri de evenimente:
* Se modifică stocul unei alimentări
* 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$]).
* 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$.
h2. 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 alimentării din nodul [$i$]).
Pe următoare $Q$ linii se vor afla evenimentele sub forma:
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 $P[~k~] S[~k~]$. Ele reprezintă părintele nodului $k$ și respectiv stocul alimentarei [$k$]. Prin convenție, $P[~1~]$ este 0.
Pe următoarele $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 distantă maximă (de la casa ei) până la o alimentară ce conține vreun aliment din lista reprezentată de key.
* $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$].
h2. 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 Joker-ului (î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$.
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$.
h2. Restricții
* $1 ≤ $N$ ≤ 150.000$
* $1 ≤ $Q$ ≤ 200.000$
* $1 ≤ value[~i~], key ≤ 1.000.000$, $1$ ≤ $i$ ≤ $N$
* $Pentru 20% din punctaj se garantează că [$N$], $Q$ ≤ 500$
* $Pentru 40% din punctaj se garantează că [$N$], $Q$ ≤ 10.000$
* $1 ≤ $Q$ ≤ 300.000$
* $1 ≤ S[~k~], 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**
* +**Se recomandă parsarea intrării**+
h2. Exemplu
table(example).
|_. alimentara.in |_. alimentara.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
h3. 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;
}
==
|_. alimentara.in |_. alimentara.out |_. imagine |
| 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
| !problema/alimentara?tree1.png!
|
table(example).
|_. alimentara.in |_. alimentara.out |_. imagine |
| 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
| !problema/alimentara?tree2.png!
|
h3. 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ă.
h3. 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.
== include(page="template/taskfooter" task_id="alimentara") ==
