Fișierul intrare/ieșire: drum.in, drum.out Sursă ad-hoc
Autor Victor Manz Adăugată de vmanzVictor Manz •vmanz
Timp execuție pe test 0.3 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate normalnormalnormalnormalnormal

Vezi soluțiile 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.in drum.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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii