Revizia anterioară Revizia următoare
| 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.
Î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 de fiecare dată 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, 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 cu o listă de cumpărături L. Joker 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 (adică S și L nu sunt prime între ele).
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 ≤ valuei, 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 |
|---|---|
| 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 |
|---|---|
| 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.
