Fişierul intrare/ieşire:evacuare.in, evacuare.outSursăLot Sovata 2014 Seniori Baraj 2
AutorVlad GavrilaAdăugată dedariusdariusMarian Darius dariusdarius
Timp execuţie pe test0.75 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Evacuare

Ca să ia o binemeritată pauză de la curăţenie, Hetty s-a dus în excursie la Praid, ca să viziteze salina din oraş. Aceasta este formată din N încăperi legate între ele prin M tuneluri bidirecţionale. Hetty a observat că în fiecare încăpere i (1≤i≤N) a fost plasat un semn pe care este scris numărul Pi al încăperii spre care trebuie să se îndrepte vizitatorii în cazul unei evacuări de urgenţă. Astfel, spunem că o încăpere i poate fi evacuată printr-o încăpere k dacă şi numai dacă una din următoarele propoziţii este adevărată:

1. Încăperea i este chiar camera care conţine ieşirea (i=k)
2. Încăperea Pi se poate evacua prin încăperea k şi există un tunel direct între încăperile i şi Pi.

În acest moment se ştie că toate încăperile din salină pot fi evacuate prin camera X. Acest lucru este însă pe cale să se schimbe, întrucât proprietarii salinei doresc să închidă ieşirea din încăperea X şi să deschidă o alta într-o încăpere Y. Întrucât salina să poată fi redeschisă, proprietarii trebuie să schimbe unele dintre semnele Pi. Un semn dintr-o încăpere i trebuie schimbat dacă numărul Pi înscrisă pe el trebuie modificat pentru ca încăperea i să poată fi evacuată prin încăperea Y. Hetty se întreabă acum care este numărul minim de semne care trebuie schimbate pentru a putea evacua toate încăperile salinei prin încăperea Y, pentru fiecare Y între 1 şi N.

Date de intrare

Fişierului de intrare evacuare.in conţine pe prima linie 3 numere naturale, N, M, şi X reprezentând numărul de încăperi, numărul de tunele din salină, respectiv camera care conţine iniţial ieşirea. Pe următoarele M linii se vor afla câte două numere naturale, reprezentând o pereche de camere care sunt unite printr-un tunel direct. Pe ultima linie se vor afla N numere naturale. Al i-lea dintre acestea reprezintă numărul Pi înscris pe semnul aflat în camera i.

Date de ieşire

In fişierul de ieşire evacuare.out se vor afişa N linii. Linia i va conţine numărul minim de semne care trebuiesc schimbate pentru ca salina să poată fi evacuată prin camera i.

Restricţii

  • 2 ≤ N ≤ 500 000
  • 1 ≤ M ≤ 600 000
  • Pentru 20% din teste M = N-1.
  • Pentru 30% din teste 2 ≤ N ≤ 2000
  • Nu există un tunel care să lege o cameră de ea însăşi.

Exemplu

evacuare.inevacuare.out
4 4 3
1 2
2 3
2 4
3 4
2 3 4 3
2
1
0
0

Explicaţie

Pentru a evacua salina prin încăperea 1, va trebui să schimbăm numărul P2 din 3 în 1 şi P3 din 4 în 2. Astfel, putem evacua cele 4 încăperi pe rutele:
1: 1
2: 2 -> 1
3: 3 -> 2 -> 1
4: 4 -> 3 -> 2 -> 1
Observăm că am putea schimba şi P4 în 2 pentru a evacua încăperea 4 pe ruta 4 -> 2 -> 1 însă această variantă nu duce la număr minim de semne schimbate.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?