Fişierul intrare/ieşire: | drum.in, drum.out | Sursă | ad-hoc |
Autor | Victor Manz | Adăugată de | |
Timp execuţie pe test | 0.3 sec | Limită de memorie | 16384 kbytes |
Scorul tău | N/A | Dificultate |
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.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 |