Fişierul intrare/ieşire:markon.in, markon.outSursăConcursul National Urmasii lui Moisil 2012, clasele 11-12
AutorCosmin-Mihai TutunaruAdăugată deandrici_cezarAndrici Cezar andrici_cezar
Timp execuţie pe test1 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Markon

Albăstrel a găsit o hartă pe care sunt reprezentate N oraşe legate între ele prin M tuneluri bidirecţionale. Fiecare oraş are asociat un număr natural cu o semnificaţie necunoscută lui Albăstrel. Ingenios din fire, acesta a folosit harta pentru a realiza un nou joc pe calculator. Jocul constă în marcarea oraşelor după o anumită regulă: un oraş A poate fi marcat numai dacă cel puţin unul dintre oraşele sale vecine B, marcat deja, are una dintre proprietăţile:
1. Valoarea asociată lui B este egală cu zero;
2. Valoarea asociată lui B este strict mai mare decât numărul oraşelor nemarcate vecine cu B.
Două oraşe sunt considerate vecine dacă există un tunel între ele. Calculatorul alege oraşul de start X iar jucătorul trebuie să înceapă marcarea cu acest oraş. Pentru a câştiga, el trebuie să marcheze un număr maxim de oraşe de pe hartă, respectând regula jocului.

Cerinţă

Ştiind că oraşul de start ales de calculator este X, scrieţi un program care să determine NR, reprezentând numărul maxim de oraşe ce pot fi marcate, precum şi cele NR oraşe, în ordinea în care acestea sunt marcate.

Date de intrare

Fişierul de intrare markon.in conţine pe prima linie trei numere naturale N, M şi X separate prin câte un spaţiu, reprezentând N - numărul de oraşe, M - numărul de tuneluri şi X - oraşul ales de calculator drept oraş de start. Pe a doua linie se află N numere separate prin câte un spaţiu, reprezentând valoarea asociată fiecărui oraş. Pe următoarele M linii se află câte două numere a şi b reprezentând faptul că între oraşele a şi b este un tunel bidirecţional.

Date de ieşire

Fişierul de ieşire markon.out are pe prima linie numărul NR, iar pe următoarele NR linii se află câte un număr reprezentând raşele în ordinea în care au fost marcate, respectând regula jocului

Restricţii

  • 2 ≤ N, M ≤ 500 000
  • 1 ≤ vi ≤ 109
  • oraşele sunt numerotate distinct de la 1 la N
  • între două oraşe diferite poate exista cel mult un tunel
  • oraşul X este singurul oraş care poate fi marcat prima dată
  • dacă există mai multe soluţii cu număr maxim, se va afişa oricare dintre acestea
  • pentru 30% din teste N, M10.000

Exemplu

markon.inmarkon.out
5 6 3
3 2 0 1 1
1 2
5 1
1 4
2 5
4 2
3 4
2
3
4

Explicaţie

Oraşul 3, ales de calculator, este marcat iniţial.
Oraşul 4 este marcat pentru că este singurul oraş care are un vecin (3), care respectă proprietatea 1.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content