Fişierul intrare/ieşire:nolife.in, nolife.outSursăLot Mehedinți 2015 - Baraj 5 Seniori
AutorMihai CiucuAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test10 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

NoGameNoLife - The Final Stage

După ce au cucerit toate cele 16 rase, Sora şi cu Shiro în sfârşit au ajuns sa îl provoace pe zeul Tet la duel. Tet a generat aleator un graf neorientat cu costuri pe muchii. La sfârşit, acesta le-a pus celor doua personaje Q întrebări de forma: care este drumul de lungime minima de la nodul x la nodul y? Pentru că ştie ca este o problema grea, el se mulţumeşte cu drumuri cât mai scurte, nu neapărat cele mai scurte.

Date de intrare

Pe prima linie a fişierului de intrare nolife.in se va afla un număr natural N (numărul de noduri) şi un numar natural M (numărul de muchii). Pe următoarele M linii vor fi trei numere x, y şi z, reprezentând faptul că există muchie între nodurile x şi y de lungime z. Pe următoarea linie se va afla un singur numar natural Q. Pe urmatoarele Q linii vor fi câte două numere, x şi y – nodurile între care vrea să găsim un drum cât mai scurt.

Date de ieşire

În fişierul de ieşire nolife.out se va afişa răspunsul pentru fiecare întrebare, câte unul pe linie. Un răspuns trebuie să descrie un drum între nodurile x şi y în felul următor: Primul număr de pe linie este numărul de noduri prin care trece drumul, urmat de nodurile în ordinea de parcurgere de la x la y. În cazul în care vreţi să nu răspundeţi la o întrebare, afişaţi doar 0 pentru aceasta.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 300.000
  • 1 ≤ Q ≤ 20.000
  • Pentru că e demiurg programator, Tet indexează indicii nodurilor de la 0 la N-1
  • Se garantează că există drum între toate nodurile din întrebari
  • Cel mai bun concurent o să o câştige pe Jibril

Exemplu

nolife.innolife.outExplicatie
5 6
1 2 1
1 4 2
4 3 4
2 3 2
4 0 3
3 0 6
4
1 2
2 0
1 4
3 4
2 1 2
4 2 1 4 0
2 1 4
2 3 4
Această soluţie primeşte punctaj complet pe test, deoarece toate drumurile sunt optime.

Punctare

Tet ştie că viaţa e o competiţie, aşa că vă va puncta în felul următor: Pentru fiecare test veţi primi un scor brut, care reprezintă suma scorurilor pentru fiecare întrebare. Pentru fiecare întrebare primiţi 1 punct dacă aflaţi un drum de lungime optimă, altfel veţi primi un număr de puncte calculat după formula:

Ştim că sună complicat, dar doar vrea să zică că primiţi maxim 0.9 puncte pentru orice scor neoptim, iar la fiecare abatere de 25% de la optim vi se înjumătăţeşte punctajul.

Atentie! Datorita imposibilitatii de a obtine scorul de 100 de puncte , evaluatorul va va oferi un punctaj normalizat cu cel al sursei oficiale.Astfel acesta va fi calculat dupa formula :  10.00 * \frac{punctaj-concurent}{punctaj-autor}

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?