Fişierul intrare/ieşire:ostrov.in, ostrov.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 17
AutorChichirim GeorgeAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test3 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ostrov

Recent, s-a descoperit o noua insula din Rusia numita Ostrov. Initial, aceasta insula nu are niciun oras sau strada construita. Datorita proprietatilor sale geografice extraordinare, multi actionari rusi vor sa investeasca in aceasta insula pentru a-si construi fabrici de apa plata magica pentru a putea sa sustina in continuare obiceiurile frumosilor ca cei din Staropramen. Astfel, exista Q operatii de forma:

  • 0 -> se construieste orasul ++N
  • 1 X nr m iar pe urmatoarele m linii cate 3 numere x, y, s ce reprezinta o strada bidirectionala intre orasele x si y de cost s, x si y apartinand celor nr orase construite reunit cu orasul X -> proprietarul orasului X construieste inca nr orase (orasele de la N+1 la N+nr) care sunt legate intre ele (orasul X cu cele nr orase noi) prin cele m strazi bidirectionale mentionate mai sus. Dupa aceasta operatie N = N + nr
  • 2 x y s -> pentru ca nu se poate ajunge din orasul x in orasul y, investitorii care detin aceste doua orase colaboreaza si construiesc o strada bidirectionala intre orasele x si y de cost s
  • 3 x y s -> costul strazii dintre orasele x si y devine s. Se garanteaza ca strada dintre x si y a fost construita anterior
  • 4 x y -> sa se afiseze costul minim al unui drum de la orasul x la orasul y, sau -1 daca nu se poate ajunge de la orasul x la orasul y

Date de intrare

Fişierul de intrare ostrov.in contine pe pe prima linie numarul Q, iar dupa aceea cele Q operatii de forma celor de mai sus.

Date de ieşire

În fişierul de ieşire ostrov.out trebuie sa se afiseze raspunsul pentru fiecare operatie de tipul 4 pe cate o linie separata.

Restricţii

  • la final N ≤ 100000
  • la final numarul de strazi ≤ 300000
  • nr ≤ 10
  • s ≤ 1000
  • numarul operatiilor de tipul 3 ≤ 10000
  • numarul operatiilor de tipul 4 ≤ 300000
  • ATENTIE! Se recomanda parsarea fisierului de intrare. Puteti folosi codul de pe siteul acesta

Exemplu

ostrov.inostrov.out
11
0
1 1 3 4
1 2 3
2 4 5
1 3 1
3 4 2
4 1 4
0
2 3 5 4
1 2 3 4
2 6 2
6 8 3
6 7 1
8 7 1
4 5 7
0
4 9 2
3 2 4 1
4 5 7
3
11
-1
10
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?