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 | 1.1 sec | Limită de memorie | 32768 KB |
Scorul tău | N/A | Dificultate |
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.
Î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.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 |
|
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 |
|
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.