Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | hiking.in, hiking.out | Sursă | AGM 2019, runda nationala |
| Autor | Vlad-Andrei Munteanu | Adăugată de |  Patrick Sava •xtreme77 |
| Timp execuţie pe test | 1 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Hiking
Poveste şi cerinţă...
Date de intrare
Fişierul de intrare hiking.in prima linie va conţine trei numere întregi pozitive N, M, Q care reprezintă numărul de sate, numărul de drumuri şi numărul de interogări(query-uri).
Următoarele M linii vor conţine trei numere întregi pozitive a, b, c care reprezintă că există un drum bidirecţional de lungime c între oraşele a şi b.
Ultimile linii Q vor conţine trei numere întregi x, y, p care reprezintă o interogare (un query) privind satele (x, y) şi paritatea lungimii drumului p.
Date de ieşire
Fişierul de ieşire hiking.out trebuie să conţină Q linii, care descriu răspunsurile pentru query-urile date (in ordine). Răspunsul este 1 dacă Artskjid poate găsi un drum cu o lungime a parităţii date între nodurile date şi 0 altfel.
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| hiking.in | hiking.out |
|---|---|
| 4 4 3 1 2 1 2 3 2 3 4 1 1 4 5 1 2 0 2 3 0 3 4 1 | 1 1 1 |
Explicaţie
...
În ţinuturile îndepărtate, a fost un munte înalt, cu multe sate înconjurate de el. Satele $ N $ ($ 1 \ leq N \ leq 100.000 ) sunt conectate prin drumuri bidirecţionale de $ M $ ( 1 \ leq M \ leq 200.000 $) cu lungimi integrale pozitive de cel mult $ 10 ^ 9 $. Interesant, sătenii nu au construit mai mult de un drum între perechi de sate şi nu au construit niciodată un drum care să înceapă şi să se termine în acelaşi sat. \\
Legendarul excursionist, Artskjid, a început să exploreze aceste sate. Desigur, el a fost uşor să găsească lungimile celor mai scurte căi între orice pereche de sate. Cu toate acestea, acum vrea să urmărească o nouă provocare. Pentru $ Q $ ($ Q \ leq 100.000 $) perechi de sate $ (x, y) $, şi un număr întreg $ p \ în \ {0, 1 \ $ $, el doreşte să ştie dacă există unele \ nu neapărat simplu} calea (adică calea poate vizita noduri sau muchii de mai multe ori) de la $ x $ la $ y $ de lungime $ l $ astfel încât $ l \ equiv p \ pmod 2 $.
