Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | markon.in, markon.out | Sursă | Concursul National Urmasii lui Moisil 2012, clasele 11-12 |
| Autor | Cosmin-Mihai Tutunaru | Adăugată de |  Andrici Cezar •andrici_cezar |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/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:
# Valoarea asociată lui B este egală cu zero;
# 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, M ≤ 10.000
Exemplu
| markon.in | markon.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.
