Runda 4: Pochodzenie

27.10.2009 - Władysław Kwaśnicki
TrudnośćTrudnośćTrudnośćTrudność

Limit czasowy: 5 sekund
Limit pamięciowy: 128 MB

Każdy chciałby czuć się ważnym, a przynajmniej ważniejszym od innych... Z tego powodu obywatele Super Bogatego Państwa prześcigają się w wymyślaniu sposobów na okazanie swojej ważności. Ostatnimi czasy w modzie jest analizowanie drzew genealogicznych. Dla przykładu, jeśli twoim przodkiem jest Mieszko, który miał syna Bolesława, to możesz czuć się wyróżnionym. A jeśli do tego Bolesław miał syna Mieszka, to dopiero możesz chodzić z głową w chmurach.

Niestety analizowanie drzew miało jedną wielką wadę — prawie każdy mógł się czuć w jakiś sposób wyróżniony. Dlaczego Marek, syn Michała ma być mniej ważny od Pawła, syna Piotra?

Aby rozwiązać problem poproszono grupę naukowców, by znaleźli systematyczny sposób oceniania drzew genealogicznych. Po wielu miesiącach gorączkowych debat ustalono pewien zbiór wzorców F = {f1, f2, .... , fk} i powiedziano, że ocena drzewa genealogicznego T to liczba wzroców z F, które pasują do T.

W naszym przypadku drzewo genealogiczne to spójny, acykliczny, nieskierowany graf T z jednym wyróżnionym wierzchołkiem, zwanym korzeniem. Każdy wierzchołek drzewa reprezentuje jedną osobę. Mając drzewo genealogiczne T możemy powiedzieć, że osobnik a jest SYNEM osobnika b, jeśli w drzewie T istnieje krawędź między a i b oraz a jest dalej od korzenia niż b. W naturalny sposób możemy powiedzieć, że b jest OJCEM a, jeśli jest SYNEM b. Również w naturalny sposób możemy powiedzieć, że jest POTOMKIEM a, jeśli jest SYNEM lub ma OJCA b, który jest POTOMKIEM a.

 

Wzorzec f opisujemy podając ciąg a1 b1 a2 b2 .... bn-1 an, gdzie ai są to imiona kolejnych osobników, natomiast bi to albo SYN, albo POTOMEK. Wzorzec f można dopasować do drzewa T, jeśli każdemu elementowi ai można przyporządkować wierzchołek drzewa tak, że:

  • jeśli wierzchołek v jest przyporządkowany do elementu ai, to osobnik odpowiadający wierzchołkowi v ma imię ai,
  • do elementu a1 przyporządkowany jest korzeń drzewa,
  • jeśli występuje trójka ai SYN ai+1 to wierzchołek przyporządkowany do ai+1 jest SYNEM wierzchołka przyporządkowanego do ai,
  • jeśli występuje trójka ai POTOMEK ai+1 to wierzchołek przyporządkowany do ai+1 jest POTOMKIEM wierzchołka przyporządkowanego do ai.

 

Dla przykładu wzorzec z pierwszego akapitu to: Mieszko SYN Bolesław SYN Mieszko.


Twoim zadaniem jest napisanie programu, który dla danego wzorca f oraz drzewa T sprawdzi, czy f da się dopasować do T.

 

Wejście

Pierwsza linia wejścia zawiera liczbę naturalną N (1<=N<=105), oznaczającą liczbę osobników w drzewie genealogicznym. Następne N linii to opis drzewa genealogicznego. W pierwszej linii opisu znajduje się pojedyńcze słowo w — imię osobnika w korzeniu. W i-szej (i>1) linii opisu drzewa znajduje się liczba p oraz słowo w (1<=p<i), gdzie w to imię osobnika, a p to numer linii opisu drzewa, w którym znajduje się jego ojciec.


Następnie na wejściu znajduje się liczba q (1<=q<=10), oznaczająca liczbę wzorców do sprawdzenia. W kolejnych liniach wejścia znajdują się opisy kolejnych wzorców. Pojedyńczy wzorzec opisujemy w następujący sposób: pierwsza linia zawiera liczbę m (1<=m<=105), oznaczającą długość wzorca. Druga linia zawiera słowo u — imię, jakie powinien mieć osobnik w korzeniu drzewa. Następne m-1 linii ma postać "SYN s" albo "POTOMEK s", gdzie s to wymagane imię, a SYN lub POTOMEK oznacza odpowiedni typ relacji na drzewie. Sumaryczna długość imion w całym wejściu nie przekracza 107 oraz każde imię ma conajwyżej 1000 znaków. Imiona składają się tylko z małych liter alfabetu angielskiego.

 

Wyjście

W kolejnych liniach wyjścia należy wypisać kolejne odpowiedzi na zapatynia. Odpowiedź na zapytanie to TAK albo NIE, w zależności od tego, czy dany wzorzec da się dopasować do drzewa genealogicznego.

Przykład

Dla danych wejściowych:

 

6
piotr
1 wladek
1 sylwia
3 pawel
4 alan
5 pawel
2
2
piotr
POTOMEK sylwia
3
piotr
SYN sylwia
SYN alan

 

poprawną odpowiedzią jest:

 

TAK
NIE

 

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com