| Fişierul intrare/ieşire: | copacsmenar.in, copacsmenar.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 17 |
| Autor | Florin Chirica | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Copacul Smenar
Andrei asculta melodiile lui Bob Marley si astfel afla despre miscarea Rastafari. Impresionat, decide sa-si creeze propria religie. Din miscarea Rastafari, va prelua doar o singura parte care i-a placut cel mai mult. De asemenea, tot atunci devine si administratorul infoarena.ro, careia, in mod nesurprinzator, ii alege culoarea verde. Tot atunci creeaza o lista cu problemele importante ale site-ului, unele idei din acea lista fiind relevante chiar si in zilele noastre.
Tanarul Rastaman vrea sa gaseasca un ritual de initiere pentru elevii sai, pentru a afla daca sunt demni de a fi parte a cultului. Astfel, un tanar pe cale de a fi initiat este dus in Templul Smecheriei, la Copacul Smenar. Copacul poate fi privit ca un arbore cu n noduri, cu costuri pe muchii. Radacina arborelui este nodul 1.
Dupa ce fumeaza pipa pacii, distantele pe arbore se modifica. Andrei ii da invatacelului o pereche de numere (A, B). Distanta dintre 2 noduri x si y se calculeaza astfel: luam fiecare muchie de pe drumul unic de la x la y. Daca muchia ne apropie de radacina, costul ei se inmulteste cu A. Daca muchia ne departeaza de radacina, costul ei se inmulteste cu B. La final, adunam numerele obtinute pentru fiecare muchie.
Andrei da m restrictii de forma (x, y, valmin, valmax): distanta intre nodul x si y este cuprinsa intre valmin si valmax. Apoi, urmeaza q query-uri de forma (A, B): Pentru o pereche (A, B) data de Andrei, sunt toate cele m restrictii indeplinite? Raspundeti corect la cele q query-uri pentru o viata mai verde.
Date de intrare
Fişierul de intrare copacsmenar.in contine pe prima linie numerele n, m si q. Pe cea de-a doua linie este data descrierea arborelui prin intermediul a 3 numere: x, y si c, reprezentand ca exista o muchie intre x si y de cost c. Urmatoarele m linii descriu restrictiile prin 4 numere: x, y, valmin, valmax, semnificand ca distanta intre nodul x si y este cuprinsa intre valmin si valmax. Urmatoarele q linii descriu query-urile, printr-o pereche de numere (A, B).
Date de ieşire
În fişierul de ieşire copacsmenar.out se vor afisa q numere. Al i-lea numar corespunde celui de-al i-lea query. In cazul in care perechea corespunzatoare query-ului respecta toate restrictiile, se va afisa 1. In caz contrar, se va afisa 0.
Restricţii
- 1 ≤ n ≤ 50
- 1 ≤ m ≤ n*(n-1)
- 1 ≤ q ≤ 100000
- Costurile muchiior sunt numere intregi care, in valoare absoluta nu depasesc 1000.
- Valorile lui valmin si valmax sunt numere intregi care, in valoare absoluta nu depasesc 10^7.
- Valorile lui A si B din query-uri sunt numere intregi care, in valoare absoluta nu depasesc 10^7.
- Perechile ordonate (x, y) din cele m restrictii sunt distincte 2 cate 2, iar x != y.
- In ciuda restrictiei specifice a lui n, problema nu are nicio legatura cu plaforma TopCoder :(
Exemplu
| copacsmenar.in | copacsmenar.out |
|---|---|
| 3 1 3 1 2 1 1 3 -1 2 3 0 10 1 1 20 10 21 10 | 1 1 0 |
Explicaţie
Avem o singura restrictie de indeplinit: distanta de la nodul 2 la nodul 3 sa fie cuprinsa intre 0 si 10. Drumul de la 2 la 3 e format din muchiile 2-1 si 1-3. Muchia 2-1 ne apropie de radacina, iar muchia 1-3 ne departeaza de ea. Deci costul drumului este costul muchie de la 2 la 1 inmultit cu A + costul muchiei de la 1 la 3 inmultit cu B. Deci costul drumului este A - B.
Trebuie ca A - B sa fie cuprins intre 0 si 10. Pentru cele 3 query-uri, rezultatele sunt 0, 10 si 11, deci doar primele 2 query-uri respecta restrictia.
