Task: DAN Dancing trip
english
CPSPC 2016, day 1. Available memory: 128 MB.
28.06.2016
After a hard year of studies, Bajtek and Bajtosia decided to visit Bajtocja, as they have always been fascinated by the folk dances of this country. They want to learn all of the dances their holidays. Bajtek and Bajtosia are now planning their trip. In Bajtocja, there are n cities. In every one of them you may learn exactly one of the k folk dances. The cities of Bajtocja are connected with a poor network of roads – each road connects two cities, and between any pair of cities there is exacly one (direct or indirect) route. Therefore, our heroes want to arrive in one particular city and end their trip in another city, such that exactly k cities are visited (each only once!), and exactly k different dances are learned. Bajtosia is asking a lot of similar questions: for a given city di , will they be able to visit di during their trip? Help Bajtek answer those questions.
Input In the first line of standard input there are three integer numbers n, k, q (1 ≤ k, q ≤ n ≤ 100 000) – the number of cities in Bajtocja, number of distinct dances possible to learn, and the number of Bajtosia’s questions. In the next line there are n integer numbers li (1 ≤ li ≤ k) – i-th number denotes the dance that may be learned in the i-th city. The next n − 1 rows describe the road network. Each of these lines consists of two integer numbers ai and bi (1 ≤ ai , bi ≤ n, ai 6= bi ) meaning that cities ai and bi are connected with a bidirectional road. Each pair of cities will appear at most once. In the next q rows there are Bajtosia’s requests. Each of them consists of one integer number di (1 ≤ di ≤ n) meaning that Bajtosia wants to visit city di on their route.
Output On the standard output you should print q rows being an answer to the Bajtosia’s requests. The i-th line should consist of one word YES if it is possible to choose such a visiting route that each of the folk dances will be learned exactly once, and the city di will be visited; or the word NO if it’s not possible to choose such a route.
Examples For the input data: 4 3 3 1 2 3 2 1 2 2 3 2 4 1 2 4
a correct result is: YES YES NO
Explanation to the examples: In first two requests it is sufficient to arrive at the city 1, then go to city 2, then to city 3 and depart. As for the third request, there isn’t any appropriate visiting route, as one would have to travel also through city 2, and thus learn a dance twice.
Grading Subtask 1 2 3
Conditions n ≤ 300 n ≤ 5000 no special conditions
Points 12 18 70
Dancing trip 1/1
Úloha: DAN Taneční výlet
czech
CPSPC 2016, Den 1. Dostupná pamět’: 128 MB.
28.06.2016
Bajtík a Ramka se rozhodli, že se konečně (po tom, co se celý rok pilně učili a nosili domů samé jedničky) o prázdninách vypraví na výlet do zaslíbené země Wifie. Jak jistě víte, tato země je světově proslulá svými lidovými tanci, které ostatně fascinují i Bajtíka s Ramkou. Ti se proto rozhodli, že se je všechny o prázdninách naučí. Bajtík a Ramka nyní plánují výlet. V zemi Wifii je n měst. V každém z nich se mohou naučit právě jeden z k wifijských lidových tanců. Města ve Wifii jsou propojena skrovnou sítí silnic, která umožňuje dostat se z libovolného města do libovolného jiného města právě jedním způsobem. Bajtík a Ramka teď přemýšlí, že svoji cestu naplánují na základě jednoho z q plánů, které už kdysi vymyslili. Každý takový plán spočívá v tom, že přijedou do libovolného města ve Wifii, dále po této zemi budou nějakou dobu cestovat a v každém městě, do nějž zavítají, se naučí tamní lidový tanec (včetně města, ve kterém začali, a města, ve kterém skončí), navíc cestou (v rámci i-tého plánu) navštíví město di a nakonec v libovolném městě skončí. Aby toho nebylo málo, Bajtík a Ramka se nechtějí stejný tanec učit dvakrát. Počet měst ve Wifii je velký, a tak tě Bajtík poprosil, abys pro každý plán ověřil, zda je možné naplánovat výlet, který splňuje výše zmíněné požadavky.
Vstup Na první řádce standardního vstupu jsou tři celá čísla n, k, q (1 ≤ k, q ≤ n ≤ 100 000) – počet měst ve Wifii, počet tanců, které se zde lze naučit, a počet Bajtíkových plánů. Na další řádce je n celých čísel li (1 ≤ li ≤ k) – i-té číslo říká, který tanec se lze naučit ve městě i. Dalších n − 1 řádků popisuje wifijskou silniční síť. Každá z řádek obsahuje dvě čísla ai a bi (1 ≤ ai , bi ≤ n, ai 6= bi ), která znamenají, že města ai a bi jsou spojena obousměrnou silnicí. Každá dvojice měst se objeví maximálně jednou. Na dalších q řádkách jsou Bajtíkovy dotazy. Každý z nich sestává z jednoho celého čísla di (1 ≤ di ≤ n), které znamená, že v rámci i-tého plánu Bajtík s Ramkou hodlají navštívit město di .
Výstup Na standardní výstup vypište q řádek s odpověďmi na Bajtíkovy dotazy. Na i-té řádce by mělo být slovo YES, pokud existuje taková cesta Wifií, že se na ní každý z jejích lidových tanců naučíte právě jednou a během výletu navštívíte město di , popřípadě by na této řádce mělo být napsáno slovo NO, jestliže žádná taková cesta neexistuje.
Příklad Pro vstupní data:
je správný výstup:
4 1 1 2 2 1 2 4
YES YES NO
3 3 2 3 2 2 3 4
Vysvětlení příkladů: V prvních dvou plánech stačí začít ve městě 1, pokračovat do města 2 a skončit ve městě 3. Během takové cesty se naučíme každý z lidových tanců právě jednou a navštívíme pro první plán potřebné město 1 a pro druhý plán potřebné město 2. Pro třetí plán žádná vyhovující cesta neexistuje, protože bychom museli projít město 2 a tak bychom se tanec dva naučili dvakrát.
Taneční výlet 1/2
Hodnocení Podúloha 1 2 3
Další omezení n ≤ 300 n ≤ 5000 žádné speciální podmínky
Body 12 18 70
Taneční výlet 2/2
Zadanie: DAN Taneczna wycieczka
polish
CPSPC 2016, dzień 1. Dostępna pamięć: 128 MB.
28.06.2016
Po ciężkim roku studiów, Bajtek z Bajtosią postanowili wybrać się na wakacje do Bajtocji, w dużej mierze ze względu na swoją fascynację tamtejszymi tańcami ludowymi. Chcą zatem tak zaplanować swój wyjazd, aby nauczyć się wszystkich możliwych tańców. W Bajtocji znajduje się n miast, a w każdym z nich można nauczyć się dokładnie jednego spośród k bajtockich tańców ludowych. Bajtockie miasta połączone są niewielką siecią dróg – drogi łączą niektóre pary miast w taki sposób, że między dowolną parą miast można (bezpośrednio lub pośrednio) przejechać na dokładnie jeden sposób. Nasi bohaterowie chcą zacząć swą wycieczkę w pewnym mieście i zakończyć ją w innym, tak aby w sumie odwiedzić dokładnie k miast (każde tylko raz!) i poznać dokładnie k różnych tańców. Bajtosia zadaje zatem Bajtkowi następującego rodzaju pytania: czy dla ustalonego miasta di da się zrealizować plan tak, aby po drodze odwiedzić di ? Czas mija, bilety lotnicze drożeją – pomóż Bajtkowi odpowiedzieć na te pytania!
Wejście W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite n, k, q (1 ≤ k, q ≤ n ≤ 100 000) – liczba miast w Bajtocji, liczba tańców, których można się nauczyć oraz liczba pytań Bajtosi. W następnym wierszu znajduje się n liczb całkowitych li (1 ≤ li ≤ k) – i-ta z nich oznacza jakiego tańca można się nauczyć w i-tym mieście. Następne n − 1 wierszy opisuje bajtocką sieć drogową. Każdy z tych wierszy składa się z dwóch liczb całkowitych ai and bi (1 ≤ ai , bi ≤ n, ai 6= bi ) oznaczających, iż miasta ai oraz bi są połączone dwukierunkową drogą. Każda taka para pojawi się na wejściu co najwyżej raz. W następnych q wierszach znajdują się pytania. Każdy z nich składa się z jednej liczby całkowitej di (1 ≤ di ≤ n) oznaczającej, że Bajtosia chciałaby wiedzieć, czy da się odwiedzić miasto o numerze di .
Wyjście Na standardowe wyjście należy wypisać q wierszy będących odpowiedziami na kolejne pytania. Wiersz i-ty powinien składać się z jednego słowa YES jeśli da się wybrać taką trasę zwiedzania by nauczyć się każdego bajtockiego tańca ludowego, dokładnie raz odwiedzając przy tym miasto di , bądź słowa NO w przeciwnym wypadku.
Przykłady Dla danych wejściowych:
poprawnym wynikiem jest:
4 1 1 2 2 1 2 4
YES YES NO
3 3 2 3 2 2 3 4
Wyjaśnienie do przykładu: W pierwszych dwóch zapytaniach wystarczy przylecieć do miasta pierwszego, następnie przejechać do miasta drugiego, a następnie do trzeciego i wylecieć z powrotem. W ten sposób nauczymy się każdego z tańców dokładnie jeden raz i odwiedzimy odpowiednio dla pierwszego zapytania miasto pierwsze, a dla drugiego zapytania miasto drugie. W przypadku ostatniego zapytania musielibyśmy przejechać przez miasto drugie i tym samym zmuszeni byśmy byli do nauczenia się tańca drugiego dwukrotnie.
Taneczna wycieczka 1/2
Ocenianie Podzadanie 1 2 3
Ograniczenia n ≤ 300 n ≤ 5000 brak dodatkowych założeń
Punkty 12 18 70
Taneczna wycieczka 2/2
Úloha: DAN Tanečný výlet
slovak
CPSPC 2016, deň 1. Pamäťový limit: 128 MB.
28.06.2016
Po ťažkom roku plnom študovania si idú Bajtek a Bajtosia užiť dovolenku v krajine Bajtocja. Sú totižto totálne fascinovaní jej kultúrnym dedičstvom – a najviac zo všetkého sa im páčia folklórne tance. Chcú sa ich naučiť všetky. V krajine je n miest, v každom z nich je možné sa naučiť práve jeden z k folklórnych tancov Bajtocje. Mestá krajiny sú pospájané chatrnou sieťou ciest – medzi každou dvojicou miest sa dá cestovať práve jedným spôsobom. Bajtek a Bajtosia teraz plánujú svoju cestu. Chcú sa vydať na túru podľa jedného z q plánov, ktoré vymysleli. i-ty plán špecifikuje mesto di , ktoré chcú navštíviť. Cestovanie podľa plánu má nasledovnú formu: 1. Bajtek a Bajtosia vstúpia do krajiny v začiatočnom meste. Ďalej cestujú po cestách do ďalších miest, a nakoniec krajinu opustia v koncovom meste. Pritom niekedy navštívia aj mesto di . 2. V každom meste, ktoré navštívia, sa naučia tancovať. To sa týka aj začiatočného a koncového mesta. Pritom sa nechcú naučiť v priebehu cesty ten istý tanec viackrát. 3. Ako sme už spomínali, chcú sa počas túry naučiť každý z k tancov. Párik by pre každý plán rád vedel, či existuje cesta, ktorý spĺňa jeho požiadavky. Počet miest v Bajcocjii je ale veľký, preto sa s touto úlohou obrátili na vás.
Vstup V prvom riadku vstupu sú tri celé čísla n, k, q – počet miest v Bajtocjii, počet rôznych tancov v krajine, a počet Bajtekových plánov. (1 ≤ k, q ≤ n ≤ 100 000) V ďalšom riadku je n celých čísel l1 , . . . , ln – i-te číslo je číslo tanca, ktorý sa dá v naučiť v i-tom meste. (Pre všetky i ∈ {1, . . . , n} platí 1 ≤ li ≤ k.) Nasledujúcich n − 1 riadkov popisuje cestnú sieť Bajtocje. Každý z týchto riadkov pozostáva z dvoch celých čísel ai a bi , znamenajúce, že mestá ai a bi sú priamo spojené obojsmernou cestou. Každá dvojica miest sa vyskytne najviac raz. (1 ≤ a1 , b1 ≤ n a ai 6= bi ) Posledných q riadkov popisuje Bajtekové plány. Každý obsahuje jedno celé číslo di , hovoriace o tom, že v i-tom pláne dovolenky chcú Bajtek a Bajtosia navštíviť mesto di . (1 ≤ di ≤ n)
Výstup Na štandardný výstup vypíšte q riadkov, i-ty z nich nech je odpoveďou na i-tu Bajtekovu požiadavku. Ak sa plán dá zrealizovať, vypíšte do toho riadku jediné slovo YES. V opačnom prípade nech obsahuje jediné slovo NO.
Príklady Pre vstup: 4 3 3 1 2 3 2 1 2 2 3 2 4 1 2 4
je správny výsledok: YES YES NO
Komentáre: Prvý aj druhý plán sa dajú splniť – nech začnú túru v meste 1, potom nech pokračujú mestom 2, a nakoniec mestom 3. Z neho krajinu opustia. Tretí plán sa splniť nedá – ak by sme niekedy navštívili mesto 4, museli by sme tiež navštíviť aj mesto 2. V ňom sa ale tiež naučíme tanec 2. Tanečný výlet 1/2
Hodnotenie Podúloha 1 2 3
Ďalšie ohraničenia n ≤ 300 n ≤ 5000 žiadne špeciálne obmedzenia
Body 12 18 70
Tanečný výlet 2/2