Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | dungeon.in, dungeon.out | Sursă | ONI 2018, clasele 11-12, ziua 2 |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 1.25 sec | Limită de memorie | 128000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dungeon
Fie G un graf neorientat cu 2 ∗ N noduri și 3 ∗ N − 2 muchii. Fiecare muchie este colorată în alb, negru sau roșu.
Se garantează următoarele:
• Există N − 1 muchii albe. Capetele lor sunt noduri din mulțimea 1, 2, . . . , N. Ele formează un arbore.
• Există N − 1 muchii negre. Capetele lor sunt noduri din mulțimea N + 1, N + 2, ..., 2 ∗ N. Ele formează un arbore.
• Există N muchii roșii. Fiecare muchie are un capăt în mulțimea 1, 2, . . . , N și celălalt capăt în mulțimea N + 1, N + 2, ..., 2 ∗ N.
Cele 2 * N capete ale muchiilor roșii sunt distincte două câte două. Cu alte cuvinte, fiecare nod
din graf are exact o muchie roșie incidentă.
Numim ciclu hamiltonian special un ciclu care:
• vizitează fiecare nod al grafului exact o dată.
• nu parcurge consecutiv două muchii de aceeași culoare.
• începe din nodul 1, iar prima muchie parcursă este de culoare roșie.
Cerinta
Afișați un ciclu hamiltonian special al grafului G sau constatați că nu există niciun astfel de ciclu.
Date de intrare
Fișierul de intrare dungeon.in va conține pe prima linie un număr natural T reprezentând numărul de teste. Pentru fiecare test pe prima linie se află valoarea N. Pe următoarele N-1 linii se găsesc perechi de valori reprezentând capetele muchiilor de culoare albă (valori de la 1 la N). Următoarele N-1 linii conţin perechi de valori ce reprezintă capetele muchiilor de culoare neagră (valori de la N + 1 la 2 ∗ N). Următoarele N perechi de valori reprezintă capetele muchiilor de culoare roşie.
Date de iesire
Fișierul de ieșire dungeon.out va conține pentru fiecare din cele T teste câte o linie cu 2 ∗ N valori reprezentând succesiunea nodurilor care formează ciclul hamiltonian special al fiecărui graf dat, respectiv valoarea -1 dacă nu există un astfel de ciclu.
Restrictii si precizari
• N ≤ 50000
• T ≤ 5
• Pentru teste in valoare de 20 puncte se garantează că N ≤ 10
• Pentru alte teste in valoare de 30 puncte se garantează că ambii arbori au forma de lanţ.
Exemplu
| dungeon.in | dungeon.out |
|---|---|
| 2 4 1 2 1 3 3 4 5 6 5 7 5 8 1 5 2 6 3 7 4 8 4 1 2 1 3 3 4 5 6 6 7 5 8 1 7 2 8 3 5 4 6 | -1 1 7 6 4 3 5 8 2 |
