Fişierul intrare/ieşire:obiective.in, obiective.outSursăpreONI 2007 Runda Finala
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Obiective

Intr-un oras mai ciudat exista N intersectii si M strazi unidirectionale ( sens unic ) intre aceste intersectii. Aceasta inseamna ca de la o intersectie la alta intre care exista strada nu se poate circula decat in unul din cele doua sensuri posibile. Analizand mai atent harta strazilor din oras, politia locala a ajuns la concluzia ca din unele intersectii nu se poate ajunge in alte intersectii mergand pe strazi doar in sensul lor de parcurgere. Primaria orasului doreste sa construiasca o gara noua si un muzeu care va atrage numerosi turisti. Amplasamentele cladirilor se vor afla in doua intersectii diferite. Datorita sistemului stradal lucrurile sunt complicate, deoarece exista posibilitatea ca turistii care au ajuns la gara sa nu poata, luand un taxi spre exemplu, ajunge la intersectia unde se afla muzeul, si, de aceea, politia va trebui sa schimbe orientarea unor strazi pentru a face acest lucru posibil.
Firma care va construi atat muzeul cat si gara pune la dispozitia primariei T oferte, prin care se specifica locatia ambelor constructii. Pentru fiecare oferta primaria trebuie sa identifice care este numarul minim de strazi carora trebuie sa le schimbe orientarea pentru ca turistii sa poata ajunge de la gara la muzeu.

Date de intrare

Datele de intrare se citesc din fisierul obiective.in. Pe prima linie a fisierului se afla doua numere naturale, N si M, numarul de intersectii si numarul de strazi unidirectionale intre aceste intersectii. Fiecare din urmatoarele M linii contine o pereche de numere naturale (u, v), cu semnificatia ca exista strada orientata de la u la v. Dupa descrierea sistemului stradal urmeaza numarul de oferte, T. Fiecare din urmatoarele T linii, pana la sfarsitul fisierului, descriu cate o oferta. O oferta este formata din indicii a doua intersectii, primul indice reprezentand intersectia unde urmeaza sa fie construita gara, iar cel de-al doilea intersectia unde se construieste muzeul.

Date de iesire

Datele de iesire se afiseaza in fisierul obiective.out. Pe linia i din acest fisier se afla numarul minim de strazi care trebuiesc reorientate pentru a exista cel putin un drum de la gara la muzeu, conform amplasarii acestor cladiri din a i-a oferta din fisierul de intrare.

Restrictii

  • 4 ≤ N ≤ 32 000
  • 5 ≤ M ≤ 64 000
  • 1 ≤ T ≤ 100 000
  • Pentru orientarea initiala a strazilor, se garanteaza ca oricum am alege 3 intersectii A, B, C, astfel incat sa putem ajunge din A in C si din B in C, atunci putem ajunge fie din A in B, fie din B in A ( posibil ambele )
  • Daca se ignora orientarea strazilor, se poate ajunge din orice intersectie in oricare alta
  • Intre oricare doua intersectii exista cel mult o strada

Exemplu

obiective.inobiective.out
5 6
1 3
2 1
3 2
2 4
4 5
3 4
3
4 3
5 1
1 5
1
2
0

Explicatie

Pentru a doua oferta, putem redirectiona strazile 4->5 si 2->4 pentru a putea ajunge din intersectia 5 in intersectia 1.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content