Fişierul intrare/ieşire:luff.in, luff.outSursă.com 2012 Runda 3
AutorMihai PopaAdăugată deedp100Edp100 •edp100
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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 Xi,Yi,Di cu semnificatia ca in graf exista o muchie bidirectionala intre nodurile Xi si Yi, avand valoarea Di. Urmeaza Q linii, fiecare continand descrierea unui query: nodi,ki.

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.

Restricţii

  • N ≤ 200.000
  • M ≤ 200.000
  • Q ≤ 100.000
  • 1 ≤ Xi,Yi,nodi ≤ N
  • 2 ≤ ki ≤ N
  • 1 ≤ Di ≤ 1.000.000.000

Exemplu

luff.inluff.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content