Diferențe pentru problema/drum între reviziile #1 si #4

drum

Drum

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

Poveste și cerință...

Se da un graf orientat cu N varfuri, numerotate de la 1 la N. Se cere sa se raspunda la Q intrebari de forma: "exista un drum optim de la 1 la N care sa treaca prin X?"

h2. Date de intrare

Fișierul de intrare $drum.in$ ...

Fișierul de intrare $drum.in$ contine pe prima linie N = numarul de varfuri ale grafului, M = numarul arcelor sale si Q = numarul de intrebari, cele trei numere fiind separate prin cate un spatiu. Pe urmatoarele M linii se afla cate doua numere naturale cuprinse intre 1 si N reprezentand extremitatile arcelor. Pe ultimele Q linii ale fisierului se afla cate un numar X, care defineste o intrebare de tipul celor descrise mai sus.

h2. Date de ieșire

În fișierul de ieșire $drum.out$ ...

În fișierul de ieșire $drum.out$ vor fi scrise pe primele Q linii raspunsurile la intrebari. In cazul in care varful X apartine ununui drum optim, in fisierul de iesire se va scrie 1, iar in caz contrar 0.

h2. Restricții

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 200 000$
* $1 ≤ Q ≤ 100 000$

h2. Exemplu
table(example).
|_. drum.in |_. drum.out |

| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.

| 6 7 4
1 2
2 6
1 3
3 4
4 6
6 1
1 5
6
2
3
5
| 1
1
0
0

|

h3. Explicație
 
...

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