#2469
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:
N-1
muchii albe. Capetele lor sunt noduri din mulțimea 1, 2, ..., N
. Ele formează un arbore.N-1
muchii negre. Capetele lor sunt noduri din mulțimea N+1, N+2, ..., 2*N
. Ele formează un arbore.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:
1
, iar prima muchie parcursă este de culoare roșie.Afișați un ciclu hamiltonian special al grafului G
sau constatați că nu există niciun astfel de ciclu.
ONI 2018 clasele XI-XII
Problema | dungeon | Operații I/O |
![]() dungeon.in /dungeon.out
|
---|---|---|---|
Limita timp | 2.5 secunde | Limita memorie |
Total: 128 MB
/
Stivă 32 MB
|
Id soluție | #43092928 | Utilizator | |
Fișier | dungeon.cpp | Dimensiune | 1.93 KB |
Data încărcării | 30 Martie 2023, 18:47 | Scor / rezultat | 0 puncte |
dungeon.cpp: In function 'bool dfs(int, bool)': dungeon.cpp:19:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (ans.size() == 2 * n) ^
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
0 | 0 secunde | Raspuns gresit. | 10 | 0 | ||
1 | 0 secunde | Raspuns gresit. | 10 | 0 | ||
2 | Depășit | Limita de timp depășită | 10 | 0 | ||
3 | Depășit | Limita de timp depășită | 10 | 0 | ||
4 | Depășit | Limita de timp depășită | 10 | 0 | ||
5 | Depășit | Limita de timp depășită | 5 | 0 | ||
6 | Depășit | Limita de timp depășită | 5 | 0 | ||
7 | Depășit | Limita de timp depășită | 5 | 0 | ||
8 | Depășit | Limita de timp depășită | 5 | 0 | ||
9 | Depășit | Limita de timp depășită | 5 | 0 | ||
10 | 0.036 secunde | Raspuns gresit. | 5 | 0 | ||
11 | 0.084 secunde | Raspuns gresit. | 10 | 0 | ||
12 | 0.084 secunde | Raspuns gresit. | 10 | 0 | ||
Punctaj total | 0 |
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema dungeon face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.