== include(page="template/taskheader" task_id="luff") ==
Bluff a gasit de aceasta data un graf neorientat cu $N$ noduri si $M$ muchii, fiecare avand o valoare asociata. Ea isi pune $Q$ intrebari de forma $(nod,k)$ si vrea sa afle pentru fiecare dintre acestea urmatorul raspuns: care este valoarea maxima $VAL$ astfel incat considerand doar muchiile cu valoare >= $VAL$ sa existe un arbore inclus in graf care sa contina cel putin $k$ noduri, printre care si nodul $nod$.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $luff.in$ va contine pe prima linie trei numere, $N,M,Q$ cu semnificatia din enunt. Urmatoarele $M$ linii vor contine cate trei numere intregi $X{~i~},Y{~i~},D{~i~}$ cu semnificatia ca in graf exista o muchie bidirectionala intre nodurile X{~i~} si Y{~i~}, avand valoarea D{~i~}. Urmeaza $Q$ linii, fiecare continand descrierea unui query: $nod{~i~},k{~i~}$.
Fişierul de intrare $luff.in$ ...
h2. Date de ieşire
În fişierul de ieşire $luff.out$ vor fi afisate $Q$ linii, reprezentand raspunsul la cate o intrebare, in ordinea aparitiei lor in fisierul de intrare. Daca pentru un query nu exista solutie, se va afisa $-1$.
În fişierul de ieşire $luff.out$ ...
h2. Restricţii
* $N ≤ 200.000$
* $M ≤ 200.000$
* $Q ≤ 100.000$
* $1 ≤ X{~i~},Y{~i~},nod{~i~} ≤ N$
* $2 ≤ k{~i~} ≤ N$
* $1 ≤ D{~i~} ≤ 1.000.000.000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. luff.in |_. luff.out |
| 7 7 3
1 2 12
2 3 15
3 4 11
4 5 12
5 7 8
6 7 7
5 6 4
2 5
7 2
4 3
| 11
8
11
|
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
== include(page="template/taskfooter" task_id="luff") ==
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="luff") ==
