Fişierul intrare/ieşire:veri.in, veri.outSursăOJI 2023, clasele 11-12
AutorVlad Adrian UlmeanuAdăugată deIvanAndreiIvan Andrei •IvanAndrei
Timp execuţie pe test1.5 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Veri

Se dă un graf orientat cu n noduri şi m muchii. Fiecare muchie are costul 1 (poate fi parcursă într-un minut). Doi "prieteni" (veri) pornesc din nodul S. Unul dintre ei vrea să ajungă în nodul A, iar celălalt vrea să ajungă în nodul B.

Cei doi prieteni se vor plimba împreună până când ciclează, adică până când vor ajunge în acelaşi nod a doua oară, notat cu Z. După ciclare, ei îşi pot continua drumurile separat. Totuşi, dacă vor, pot să meargă amândoi în
continuare pe acelaşi drum: doar dispare obligaţia de a merge împreună.

Fiecare dintre ei trebuie să-şi termine drumul doar după ciclare, adică după ce nu mai sunt obligaţi să meargă împreună.
Totuşi, este în regulă dacă drumul unuia se termină exact în nodul în care au ciclat (adică ciclează în A sau B).

Care este numărul minim de minute necesar, astfel încât să fie posibil ca amândoi să ajungă la destinaţiile lor, în timpul alocat, în A, respectiv B?

Cu alte cuvinte, dacă cei doi veri ciclează pentru prima oară după exact t minute, apoi îşi continuă drumurile pentru alte tA, respectiv tB minute, vrem să aflăm valoarea minimă a lui max(t + tA, t + tB).

Există două tipuri de cerinţe, reprezentate printr-un număr c:

  • Dacă c = 1, trebuie calculată valoarea minimă a lui max(t + tA, t + tB).
  • Dacă c = 2, trebuie afişat un triplet de drumuri care poate fi urmat de cei doi veri (drumul comun din S până în Z, drum urmat ulterior de primul văr din Z până în A, drum urmat ulterior de al doilea văr din Z până în B), astfel încât valoarea asociată drumurilor, adică max(t + tA, t + tB) să fie minimă. Orice triplet corect cu valoarea asociată minimă poate fi afişat.

Date de intrare

Pe prima linie se găseşte c. Pe a doua linie se găsesc doi întregi n şi m. Pe a treia linie se găsesc trei întregi S, A şi B.

Pe următoarele m linii se găsesc câte doi întregi X şi Y , reprezentând că există o muchie direcţionată de la nodul X la nodul Y, care poate fi parcursă într-un minut (de cost 1).

Date de ieşire

Dacă c = 1, afişaţi un singur număr, valoarea minimă a lui max(t + tA, t + tB).

Dacă c = 2, afişaţi trei drumuri. Primul drum este format de la S până la Z. Al doilea drum este format de la Z până la A. Al treilea drum este format de la Z până la B, unde S, A, B, Z sunt definite anterior.

Fiecare drum se va tipări pe două linii separate.

  • Pe prima linie va apărea lungimea drumului, adică numărul de muchii.
  • Pe a doua linie vor apărea nodurile drumului, separate prin câte un spaţiu.

Valoarea asociată drumurilor, adică max(t + tA, t + tB), trebuie să fie minimă.

Restricţii

  • 1 ≤ S, A, B, Z ≤ n ≤ 5 000
  • Nodurile sunt numerotate de la 1 la n.
  • A ≠ B
  • 1 ≤ n ≤ m(m - 1)
  • Se garantează că pentru orice test dat spre rezolvare există cel puţin o soluţie.
  • Nu există muchii de la un nod la el însuşi. Există maxim o muchie orientată între oricare două noduri distincte.
  • Dacă verii se despart în A, primul văr poate să nu mai facă nimic (drumul lui ulterior ar avea 0 muchii şi l-ar conţine doar pe A: vezi exemplul 3). Analog pentru B.
  • Pentru fiecare subtask, testele cu c = 1 vor conta pentru 60% din punctaj.
#PunctajRestricţii
130n ≤ 500, m = n şi toate muchiile sunt de forma i → (i mod n) + 1, unde i ∈ {1, ..., n}.
250n ≤ 500
320n ≤ 5 000 şi m ≤ 4n

Exemple şi Explicaţii

veri.inveri.out
2
7 8
1 3 4
1 2
2 5
5 7
7 6
6 7
6 5
5 3
7 4
5
1 2 5 7 6 5
1
5 3
2
5 7 4

Figura 1: Drumul urmat în comun de cei doi este 1 → 2 → 5 → 7 → 6 → 5. Drumul urmat de primul văr în continuare este 5 → 3. Drumul continuat de al doilea văr este 5 → 7 → 4. Astfel, primul văr are nevoie de 6 minute pentru a ajunge în A, iar al doilea de 7 minute pentru a ajunge în B, deci răspunsul pentru c = 1 este 7. Cei doi ar fi putut să cicleze în 7, dacă ar fi urmat drumul 1 → 2 → 5 → 7 → 6 → 7. Totuşi, deşi al doilea văr ar fi ajuns în B în doar 6 minute (7 → 4), primul văr ar fi avut nevoie de cel puţin 8 minute ca să ajungă în A (7 → 6 → 5 → 3).

veri.inveri.out
2
7 8
1 2 5
1 3
1 4
3 2
4 5
6 4
7 3
3 6
4 7
5
1 4 7 3 6 4
3
4 7 3 2
1
4 5

Figura 2: Răspunsul corect pentru c = 1 este 8. Pentru acest exemplu există două soluţii corecte. A doua soluţie este tripletul de drumuri (1 → 3 → 6 → 4 → 7 → 3, 3 → 2, 3 → 6 → 4 → 5).

veri.inveri.out
2
5 6
1 3 5
1 2
2 3
3 4
4 3
3 1
3 5
4
1 2 3 4 3
0
3
1
3 5

Figura 3: Răspunsul corect pentru c = 1 este 5. Este folosit un ciclu care se termină în A = 3.

veri.inveri.out
1
4 4
1 2 4
1 3
3 2
2 3
2 4
5

Figura 4: Pentru c = 2, singurul triplet corect de drumuri este (1 → 3 → 2 → 3, 3 → 2, 3 → 2 → 4).

Atenţie! Tripletul (1 → 3 → 2 → 3 → 2, 2, 2 → 4) este greşit, deoarece primul nod vizitat a doua oară nu este 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?