Fişierul intrare/ieşire:marvel.in, marvel.outSursăAlgoritmiada 2016 - Runda 4 - Seniors
AutorEugenie Daniel PosdarascuAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.375 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Marvel

Toata lumea stie ca Marvel este cel mai mare univers de super-eroi. In timp ce facea niste kebab, Deadpool a inceput sa se joace un nou joc pe telefon. Jocul are N misiuni numerotate de la 1 la N si incepe de la misiunea 1. De fiecare data cand termini o misiune, este posibil sa deblochezi alte misiuni sau sa te opresti. Putem reprezenta jocul drept un graf aciclic cu N noduri, muchia de la a la b reprezentand faptul ca misiunea b este deblocata in momentul in care misiunea a este terminata. Un story-line este o insiruire de misiuni în care fiecare misiune, înafară de ultima, este urmată de o misiune nou-eliberată (altfel spus, un lant in graf care porneste din nodul 1). La finalul fiecarei misuni, jucatorul trebuie sa se bata cu un inamic. Pentru fiecare misiune se cunoaste indicele acestui inamic (un numar natural de la 1 la K).

Deadpool are o lista cu P prieteni, toţi fiind inamici de-ai săi (asta-i viaţa, ce să faci). El doreste sa parcurga un story-line astfel incat acea lista de prieteni sa apara ca subsir in secventa inamicilor cu care se confrunta. Voi trebuie sa spuneti pentru cate din cele N misiuni exista un astfel de story-line care se termina cu misiunea respectivă.

Lista poate sa contina acelasi prieten de mai multe ori (Deadpool se distreaza cateodata prea bine cu prietenii lui).

Date de intrare

Fişierul de intrare marvel.in va contine pe prima linie 4 numere N, M, K, si P reprezentand numarul de noduri, numarul de muchii, numarul de inamici si numarul de prieteni din lista lui Deadpool. Următoarea linie va conţine N numere, reprezentând indicii inamicilor din fiecare nod. A treia linie va conţine P numere, reprezentând indicii prietenilor doriţi de Deadpool în lupta sa, în ordinea în care aceştia trebuie întâlniţi. Pe următoarele M linii se afla cate 2 numere naturale a si b reprezentand faptul ca misiunea b este deblocata in momentul in care misiunea a este terminata.

Date de ieşire

Fişierul de ieşire marvel.out va contine un singur numar natural reprezentand numarul de noduri din cele N pentru care exista un story-line cu proprietatea ceruta. Pe cea de a doua linie se vor afla indicii nodurilor respective, în ordine crescătoare.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 300.000
  • 1 ≤ P ≤ N
  • 1 ≤ K ≤ N
  • O misiune se consideră eliberată dacă s-a efectuat cel puţin una din misiunile care o pot elibera.
  • Un subşir B al unui şir A se obţine ştergând anumite elemente din A, posibil niciunul sau posibil toate. Elementele neşterse rămân în aceeaşi ordine.

Exemplu

marvel.inmarvel.out
6 7 3 2
2 1 3 2 2 1
3 2
1 2
1 3
2 4
3 6
6 4
3 4
3 5
2
4 5

Pentru misiunea 4 există lanţul de misiuni 1 -> 3 -> 6 -> 4, care are inamicii asociaţi 2 3 1 2. Şirul 3 2 apare ca subşir al acestuia.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?