Fişierul intrare/ieşire:gossips.in, gossips.outSursăRMMS 2011 - Ziua 2
AutorAndrei ParvuAdăugată deandrei.12Andrei Parvu andrei.12
Timp execuţie pe test0.75 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Gossips

Poli este în primul an la facultate. Chiar dacă s-a dus la una dintre cele mai bune universităţi ea şi-a dat seama repede că toţi colegii săi s-au împărţit în N grupuri de prieteni, principalul scop al acestor grupuri fiind răspândirea bârfelor. Poli ştie că fiecare grup i este format din unul sau mai multe subgrupuri astfel încât orice subgrup poate face parte doar dintr-un singur grup. Să presupunem că un grup i află o bârfă despre un grup j: atunci toate subgrupurile lui i (şi subgrupurile subgrupurilor acestuia, etc.) şi toate grupurile din care i face parte ştiu bârfa despre grupul j. De asemenea, toate aceste grupuri ştiu bârfa despre fiecare grup pentru care grupul j este parte a sa (dar nu ştiu nimic despre subgrupurile lui j, deoarece acei membri s-ar putea să nu fie implicaţi în bârfă).
Deoarece Poli este prietenă cu cu fiecare din colegii săi, ea ştie atunci când apare o bârfa (adică atunci când un grup i găseşte o bârfă despre un grup j). Acum ea doreşte să poată răspunde rapid la întrebări de forma: “Ştie grupul i o bârfă despre grupul j?”.
Din păcate facultatea lui Poli este cam mare, aşa că voi trebuie să o ajutaţi.

Date de intrare

Pe prima linie a fişierului gossips.in se află trei numere N – numărul de grupuri, M – numărul de relaţii între grupuri şi Q – numărul de query-uri.
Următoarele M linii sunt de forma a b semnificând că grupul b face parte din grupul a.
Următoarele Q linii au fiecare trei numere: s – tipul query-ului şi x y – două grupuri, Dacă s este 1 atunci trebuie să răspundeţi cu “YES” dacă grupul x ştie cel putin o bârfă despre grupul y sau “NO” în caz contrar. Daca s este 2 atunci grupul x tocmai a aflat o bârfa despre grupul y.

Date de ieşire

Fişierul gossips.out trebuie să conţină mai multe linii, câte una pentru fiecare query de tipul 1, fiecare linie fiind “YES” sau “NO” (fără ghilimele).

Restricţii

  • 1 ≤ N, Q ≤ 100.000
  • 1 ≤ M < N
  • 1 ≤ x, y ≤ N
  • dacă un grup i cunoaşte o bârfă despre un grup j nu înseamnă că şi j cunoaşte o bârfă despre i

Exemplu

gossips.ingossips.out
9 7 7
6 1
6 2
7 6
7 3
8 4
8 5
9 7
2 6 4
2 8 6
1 2 4
1 2 5
1 4 7
1 8 1
1 5 9
YES
NO
YES
NO
YES
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content