Powder s-a strecurat în biroul lui Jayce din Piltover pentru a șterpeli tehnologie avansată, și acum dorește să ajungă înapoi în Zaun. Din păcate, multe intersecții din Piltover sunt pline de polițiști investigând diferite fărădelegi. Ea știe că va fi prinsă dacă trece prin cel puțin 3 intersecții cu polițiștii (a 3-a oară e cu ghinion), și dorește să ajungă cât mai repede la intrarea secretă către orașul subteran Zaun. Știind că harta orașului este codificată prin N numere (de la 1 la N) reprezentând intersecțiile, și prin M perechi de numere (reprezentând o stradă prin numerele de ordine ale intersecțiilor din capetele străzii), aflați următoarele informații:
1. Numărul minim de intersecții prin care trece Powder pentru a ajunge la intrarea în Zaun de la biroul lui Jayce
2. În cazul în care sora lui Powder, numită Vi, reușește să ademenească toți polițiștii în intersecția cu numărul de ordine V, care este cel mai scurt drum (ca număr de intersecții) pe care Powder trebuie să îl parcurgă ca să ajungă la intrarea în Zaun de la biroul lui Jayce, dacă nu are voie să ajungă în intersecția V (ar fi prinsă de polițiștii de acolo)? Evident, în celelalte intersecții nu se mai regăsesc polițiști (au plecat toți la intersecția V în acest caz).
Se vor afla pe prima linie 4 numere N, M, K, V, reprezentând numărul de intersecții, numărul de străzi, numărul de polițiști și intersecția specială în care vor fi ademeniți polițiștii la subpunctul 2) . Pe următoarele M linii se va afla câte o pereche de numere de la 1 la N, această pereche reprezentând strada respectivă, iar după acestea se vor afla pe o singură linie cele K intersecții în care se află inițial polițiștii.
Se vor afișa două numere separate prin spațiu, primul fiind răspunsul la subpunctul 1), iar al doilea la subpunctul 2) .
Pentru 20 de puncte, numărul de polițiști va fi < 3
Pentru alte 20 de puncte, numărul de polițiști va fi <= 10 și N, M <= 1000
Pentru alte 20 de puncte, N, M <= 4000
Pentru alte 20 de puncte, N, M <= 30000
Pentru restul de 20 de puncte nu vor exista restricții adiționale.
Pentru fiecare test, dacă se răspunde corect la o singură cerință, veți primi jumatate din valoarea testului dacă sunt afișate două numere în fișierul de intrare, în ordinea corectă.
9 10 4 6 1 2 1 3 2 4 3 5 5 6 5 7 7 8 6 9 8 9 4 5 3 5 6 7
6 6
Biroul lui Jayce este considerat ca fiind intersecția 1, iar intrarea în Zaun intersecția cu numărul N.
1 <= N, M <= 100000
În cazul în care nu este posibilă realizarea unui drum corect la vreo cerință, se va afișa -1 pentru subtaskul respectiv.
Powder vrea să spargă seiful lui Jayce pentru a obține niște documente foarte importante, dar odată ajunsă în fața seifului descoperă că acesta are un sistem de deblocare aparte, format din N pini de presiune, fiecare din ei necesitând o secundă pentru a îl fixa în poziția cuvenită. Ea a observat că fiecare pin are câțiva pini care sunt legați de el ca alarmă.
Pentru a putea deschide seiful, este necesară activarea primului pin, dar din păcate, fiecare pin i activat va porni alarma dacă nu are cel puțin K[i] alți pini deja activați din cei care îi pot provoca alarma. Așadar, ea vă roagă să îi spuneți de câte secunde are nevoie ca să poată debloca seiful fără să pornească vreo alarmă.
Pe prima linie se va afla N, numărul de pini. Pe fiecare din următoarele i linii se vor afla două numere Nr[i] și K[i], reprezentând numărul de pini conectați ca alarmă la pinul i, precum și numărul minim dintre aceștia necesari să fie deja apăsați pentru ca să poată fi apăsat pinul i fără a declanșa alarma. Pe fiecare astfel de linie urmează Nr[i] astfel de valori, reprezentând indicii pinurilor cu care este conectat pinul i.
Se va afișa numărul de secunde minim pentru activarea pinului 1.
Pentru 40 de puncte N <= 100.
10 3 2 2 3 4 2 1 5 7 3 2 6 8 9 1 0 10 0 0 0 0 0 0 0 0 0 0 0 0
4
Se vor acționa, în această ordine, pinii 7, 4, 2 și 1.