Fişierul intrare/ieşire:tequila.in, tequila.outSursăJunior Challenge 2016
AutorAlexandru Niculae, Costin OncescuAdăugată deJuniorChallenge2015JuniorChallenge2016 JuniorChallenge2015
Timp execuţie pe test0.35 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tequila

Intors acasa de la ONI, Antonio se plimba prin Gradina Publica din Barlad impreuna cu cel mai bun prieten al sau, Zetul.
Antonio ii spune lui Zetul urmatoarea problema, care se va da la JBOI 2016 (informatie sigura, aflata de Antonio):

Antonio si-a imaginat o firma cu N angajati, numerotati de la 1 la N. Fiecare angajat al firmei are cate un sef direct (in afara de seful suprem), iar fiecare angajat il are ca sef indirect pe seful suprem. Se mai stie ca fiecare membru al firmei (inclusiv seful suprem) are o valoare asociata,  val_X .

Exista  2 tipuri de operatii:

  • Update: Noua valoarea asociata angajatului  X va fi  Y ;
  • Query: Cat timp seful suprem nu este concediat, Zetul alege la intamplare un angajat  X si va fi nevoit sa bea  val_X shot-uri de tequila, iar apoi il va concedia atat pe  X cat si pe toti angajatii care il au ca sef indirect pe  X . Antonio este curios cate shot-uri de tequila va bea Zetul in medie (eng. "expected value").

Cerinta

Pentru valorile asociate initial, cat si dupa fiecare operatie de update, Antonio va cere sa aflati raspunsul la operatia de query.

Date de intrare

Fisierul de intrare tequila.in va contine pe prima linie doua numere naturale  N si  M , reprezantand numarul de angajati ai firmei si, respectiv, numarul de update-uri;
Urmatoarea linie va contine  N numere naturale - pentru fiecare angajat  X ( 1 \leq X \leq N ) valoarea asociata initial,  val_X ;
Urmatoarele  N linii vor descrie firma - pentru fiecare angajat  X ( 1 \leq X \leq N ), seful direct al acestuia;
Urmatoarele  M linii vor descrie operatiile de update sub forma:  X \: Y (noua valoare asociata lui  X este  Y , echivalent cu  val_X = Y ).

Date de ieşire

Fişierul de ieşire tequila.out va contine  M + 1 linii, reprezentand raspunsul pentru fiecare query in parte.

Restricţii si precizari

  •  1 \leq val_X \leq 100 \: 000 \: (1 \leq X \leq N)
  • Seful suprem va avea seful direct codificat cu  -1 . (nu este neaparat angajatul codificat cu  1 )
  • Fie  Y seful direct al angajatului  X . Spunem ca un angajat este sef indirect al lui  X daca acesta este fie  Y , fie un sef indirect al lui  Y .
  • Dupa o operatie de query, Zetul va angaja la loc toti membrii firmei.
  • Rezultatul afisat se va considera corect daca si numai daca fie eroarea absoluta, fie cea relativa este pana in  10^-^5 . Mai exact, fie  \(\mid rezultat_c_o_m_i_s_i_e - rezultat_c_o_n_c_u_r_e_n_t \mid \leq 10^-^5\) , fie  \(\frac{\mid relzultat_c_o_m_i_s_i_e - rezultat_c_o_n_c_u_r_e_n_t \mid}{rezultat_c_o_m_i_s_i_e} \leq 10^-^5\) .
  • Antonio foloseste mult expresia "pe mangleala" si cuvantul "gen".
  • Subtask 1 (30 puncte):  1 \leq N \leq 20 ,  M = 0 (Feedback testul  2 )
  • Subtask 2 (20 puncte):  1 \leq N \cdot M \leq 4 \: 000 \: 000$ ,  1 \leq M \leq 4 \: 000 si nu vor exista  2 angajati cu acelasi sef direct (Feedback testul  9 )
  • Subtask 3 (50 puncte):  1 \leq N \leq 100 \: 000 ,  1 \leq M \leq 100 \: 000 (Feedback testul  15 )

Exemplu

tequila.intequila.out
3 1
1 1 1
-1
1
1
1 2
2.00000
3.00000
3 0
1 1 1
2
-1
1
1.83333

Explicaţie

Pentru testul  1 , exista  5 posibilitati de a concedia angajatii (considerand si ordinea concedierilor):

  1. Angajatul 1 cu probabilitatea  \(\frac{1}{3}\) - in acest caz Zetul va bea  val_1 shot-uri;
  2. Angajatii 2, 1 cu probabilitatea  \(\frac{1}{3} \cdot \frac{1}{2}\) - in acest caz Zetul va bea  val_2 + val_1 shot-uri;
  3. Angajatii 3, 1 cu probabilitatea  \(\frac{1}{3} \cdot \frac{1}{2}\) - in acest caz Zetul va bea  val_3 + val_1 shot-uri;
  4. Angajatii 2, 3, 1 cu probabilitatea  \(\frac{1}{3} \cdot \frac{1}{2} \cdot 1\) - in acest caz Zetul va bea  val_2 + val_3 + val_1 shot-uri;
  5. Angajatii 3, 2, 1 cu probabilitatea  \(\frac{1}{3} \cdot \frac{1}{2} \cdot 1\) - in acest caz Zetul va bea  val_3 + val_2 + val_1 shot-uri;

Asadar:

  1. Pentru valorile asociate initial, Zetul va bea in medie  \(\frac{1}{3} + \frac{2}{6} + \frac{2}{6} + \frac{3}{6} + \frac{3}{6} = 2\) shot-uri de tequila;
  2. Dupa primul update, Zetul va bea in medie  \[\frac{2}{3} + \frac{3}{6} + \frac{3}{6} + \frac{4}{6} + \frac{4}{6} = 3\] shot-uri de tequila;
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?