== 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!
Poveste și cerință...
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 $S[~k~]$ (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$.
h2. Date de intrare
Fișierul de intrare $alimentara.in$ ...
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 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$ ...
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") ==
