Diferențe pentru problema/orase între reviziile #23 si #4

Orașe

Orase

== include(page="template/taskheader" task_id="orase") ==

Dorinel este un inginer la o firmă de software. Șefa lui, pe nume Nushaka, i-a dat temă să facă un program mai special. Se dau N localități, numerotate de la $1$ la [$N$]. Aceste orașe sunt conectate prin $M$ șosele (o șosea este descrisă prin $2$ numere $x$ și $y$ ce reprezintă capetele drumului). Un județ este format din mai multe orașe, conectate prin una sau mai multe șosele. Un oraș izolat este un oraș ce nu este conectat la nici un alt oraș.

Dorinel este un inginer la o firmă de software. Șefa lui, pe nume Nușa, i-a dat temă să facă un program mai special. Se dau N localități, numerotate de la $1$ la [$N$]. Aceste orașe sunt conectate prin $M$ șosele (o șosea este descrisă prin $2$ numere $x$ și $y$ ce reprezintă capetele drumului). Un județ este format din mai multe orașe, conectate prin una sau mai multe șosele). Un oraș izolat este un oraș ce nu este conectat la nici un alt oraș.

h2. Cerință

h2. Date de intrare

Fișierul de intrare $orase.in$ conține pe prima linie două numere $N$ și [$M$]. Următoarele $M$ linii descriu șoselele. Pe linia $M + 2$ se dă un număr [$T$], care reprezintă numărul de întrebări de la cerința [$2$], iar apoi pe următoarele $T$ linii se dau două numere $x$ și $y$ ce reprezintă întrebarea $(x, y)$.

Fișierul de intrare $orase.in$ conține pe prima linie două numere $N$ și [$M$]. Următoarele $M$ linii descriu șoselele. Pe linia $M + 1$ se dă un număr [$T$], care reprezintă numărul de întrebări de la cerința [$2$], iar apoi pe următoarele $T$ linii se dau două numere $x$ și $y$ ce reprezintă întrebarea $(x, y)$.

h2. Date de ieșire

h2. Restricții și precizări

* $1 ≤ N ≤ 100000$
* $1 ≤ M ≤ 25000$

* $1 ≤ N, M ≤ 100000$

* $1 ≤ T ≤ 1000$

* $1 ≤ x, y ≤ N$
* Un județ este format din unul sau mai multe orașe.
* Dacă pentru cerința $2$ nu se poate ajunge din $x$ în $y$ se va afișa $-1$.
* Pentru cerința $1$ se acordă $30%$ din punctaj.
* Pentru cerința $2$ se acordă $30%$ din punctaj.
* Pentru cerința $3$ se acordă $40%$ din punctaj.
* Dacă rezolvați toate cerințele, Dorinel vă va răsplăti cu $100$ de puncte și poate și cu $1$ leu (nu promite nimic).

* $1 ≤ x, y ≤ N $
* Un județ poate fi format doar dintr-un oraș.

h2. Exemplu
table(example).

|_. orase.in |_. orase.out |_. Imagine |
| 7 5
1 2
3 7
2 4
4 5
2 5
3
3 7
1 4
3 6
| 1
1
2
-1
3
| !problema/orase?31.jpg!
|

|_. orase.in |_. orase.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|

h3. Explicație

Singurul oraș izolat este [$6$]. Pentru a ajunge din $3$ în $7$ se folosește șoseaua $3-7$. Pentru a ajunge din $1$ în $4$ se folosesc șoselele $1-2$ și $2-4$. Cum $6$ este izolat, nu putem ajunge din $3$ în [$6$]. Cele $3$ județe sunt $1-2-4-5$, $3-7$ și [$6$].

...

== include(page="template/taskfooter" task_id="orase") ==