Fişierul intrare/ieşire:drum.in, drum.outSursăad-hoc
AutorVictor ManzAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test0.3 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Drum

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?"

Date de intrare

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.

Date de ieşire

Î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.

Restricţii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 200 000
  • 1 ≤ Q ≤ 100 000

Exemplu

drum.indrum.out
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici