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

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 1 categorii