Runda 35 - Pomidory

28.06.2010 - Damian Rusak
TrudnośćTrudnośćTrudność

 

Zawody Stałe, runda 35

Limit czasowy: 5s; Limit pamięciowy: 128MB


Pomidory

 

Hodowla pomidorów to wyczerpujące zajęcie. Na szczęście znajomość reguł zasad dobrego hodowcy to pierwszy krok do osiągnięcia sukcesu. Andrzej jest inteligentnym i wykwalifikowanym rolnikiem z bogatym życiorysem i nikogo w okolicy nie zdziwiło to, że pierwszy zdobył sadzonki nowej odmiary - Pomidora Podczepianego, dającego wyśmienite plony. Jednak aby nabrzmiały sokiem dojrzałe owoce potrzebna jest intentywna pielęgnacja.

Andrzej ma całą instrukcję, w której krok po kroku jest opisane jak należy podczepiać pewne sadzonki pomidora do innych. Ponadto musi wciąż kontrolować, jak daleko od korzenia sadzonki znajdują się pewne ważne owoce. Każda sadzonka Pomidora Podczepianego wygląda jak drzewko -  składa się z pnączy i owoców. Każda sadzonka jest umocowana przy suficie szklarni i na początku instrukcja każe uwiązać tak każdą sadzonkę (składającą się tylko z jednego owocu) osobno. Instrukcje mogą być dwojakiego rodzaju:

1) Odczep jedną z sadzonek od sufitu i podczep ją pnączem do pewnego owocu innej sadzonki.

2) Zbadaj, na jakiej głębokości (jak wiele pnączy trzeba przejść aż do sufitu) znajduje się wskazany owoc.

Innymi słowy, jeśli wyobrazić sobie sadzonki jako drzewa, to instrukcja 1) każe nam podczepić korzeń jednego z drzew do pewnego wierzchołka drugiego drzewa, zaś instrukcja 2) każe nam zbadać głębokość wierzchołka w drzewie. Andzej ma problem z odczytaniem instrukcji, poprosił więc Ciebie o pomoc i znalezienie dla niego odpowiedzi na instrukcje drugiego typu.

 

Wejście:

Pierwsza linia wejścia zawiera liczby całkowite $ n $ i $ m $ - kolejno liczbę początkowych pojedyńczych sadzonek oraz liczbę instrukcji do wykonania ($ 1 \leq n,m \leq 10^{6} $). Załóż, że pomidory, stanowiące początkowe sadzonki, są kolejno ponumerowane od $ 1 $ do $ n $. W kolejnych $ m $ liniach znajdują się instrukcje postaci:

1) P $ a $ $ b $  - oznaczające, że należy podczepić całą sadzonkę zawierającą pomidor o numerze $ a $ do pomidora o numerze $ b $. Jeżeli $ a $ i $ b $ należą do tej samej sadzonki, instrukcję należy zignorować.

2) D $ a $   -  oznaczające, że należy wypisać głębokość pomidora o numerze $ a $. Przez głębokość rozumiemy tu odległość pomidora (ile pnączy w górę należy pokonać), aby dotrzeć do sufitu, gdzie sadzonka jest poczepiona.

Wyjście:

Dla każdej instrukcji postaci D $ a $ należy wypisać, aktualną w momencie pojawienia się instrukcji, głębokość pomidora o numerze $ a $ w nowej linii.

Przykład:

Wejście:

8 8
P 2 1
P 3 1
P 4 1
P 5 4
P 8 7
P 8 4
D 6
D 8

Wyjście:

1

Rysunek powyżej prezentuje ostatnie trzy instrukcje, jeśli przyjmniemy, że wierzchołki 6 i 8 oznaczone są niebieskimi okręgami.

 

 

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzas
1Przemysław Derengowski1082:15:58
2Arek Wróbel10150:17:31
3Miłosz Łakomy10182:37:08
4Bartek Dudek10291:16:06
5Wojciech Dyżewski10844:17:52
6Maciej Szeptuch104046:10:16
7Piotr Jagiełło104481:42:36
8Witold Długosz106725:15:41
9Krzysztof Drab707:36:52
10Adam Tażyk136:44:13
5
Twoja ocena: Brak Ocena: 5 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com