Fișierul intrare/ieșire drum.in, drum.out Sursă ad-hoc
Autor Victor Manz Adăugată de avatar vmanz Victor Manz • vmanz
Timp de execuție pe test 0.3 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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