Fişierul intrare/ieşire:delay.in, delay.outSursăLot 2002
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.325 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Delay

Testele pentru aceasta problema nu sunt destul de bine construite pentru a departaja corect solutii ineficiente sau gresite.
Intra aici daca vrei sa ne ajuti sa imbunatatim calitatea testelor pentru aceasta problema!

Gigel a cumparat N calculatoare cu care vrea sa deschida un Internet Cafe. Pentru aceasta, el trebuie sa conecteze toate calculatoarele in retea, in asa fel incat oricare doua calculatoare sa poata comunica intre ele, direct sau indirect. Comunicatia dintre calculatoare se realizeaza prin intermediul cablurilor de legatura. Un cablu leaga doua calculatoare, iar transferul de date prin cablu se poate realiza in ambele sensuri. Fiind la inceput si neavand prea multi bani, Gigel a legat calculatoarele intre ele astfel incat intre oricare doua calculatoare exista un singur traseu pe care se pot transmite date.
Curand si-a dat seama ca transferul de date se realizeaza cu viteza foarte mica. Acest lucru se datoreaza faptului ca fiecare pachet de date care trece prin calculatorul i este pus sa astepte un timp Ti. In aceste conditii, timpul dupa care un pachet de date ajunge de la un calculator la altul este egal cu suma timpilor de asteptare ai fiecarui calculator de pe traseu (inclusiv ai calculatoarelor sursa si destinatie).
Din cand in cand, configuratia anumitor calculatoare este modificata si timpii de asteptare corespunzatori acelor calculatoare se schimba. Cum Gigel are grija foarte mare de calculatoarele sale, el trebuie sa fie mereu informat in legatura cu starea retelei. Mai precis, el trebuie sa poata afla repede care este timpul de transmitere a unui pachet de date intre oricare doua calculatoare din reteaua sa.

Cerinta

Scrieti un program care trateaza in mod eficient urmatoarele doua tipuri de operatii:

  • tipul 1: modificarea timpului de asteptare al unui calculator
  • tipul 2: determinarea timpului de transmitere a unui pachet de date intre doua calculatoare specificate.

Date de Intrare

Pe prima linie a fisierului de intrare delay.in se afla numarul N de calculatoare. Pe fiecare dintre urmatoarele N linii se afla cate un numar intreg Ti, reprezentand timpul initial de asteptare al calculatorului corespunzator. Pe urmatoarele N-1 linii se afla cate doua numere intregi a si b, reprezentand numerele a doua calculatoare legate printr-un cablu direct. Pe urmatoarea linie se afla numarul intreg M, reprezentand numarul de operatii descrise in continuare. Fiecare dintre urmatoarele M linii contine cate 3 numere intregi separate prin spatii: a b c.

  • Daca a=1, atunci b reprezinta numarul de ordine al unui calculator nou configurat, iar c reprezinta noul timp de asteptare al calculatorului b
  • Daca a=2, atunci b si c reprezinta numerele de ordine a doua calculatoare diferite, iar programul va trebui sa afiseze in fisierul de iesire timpul de transmitere a unui pachet de date intre calculatoarele b si c

Date de Iesire

In fisierul delay.out veti afisa, pe cate o linie separata, timpii determinati in cazul fiecarei operatii de tipul 2, in ordinea in care sunt intalnite in fisierul de intrare. Atunci cand calculati timpul de transmitere a unui pachet de date intre doua calculatoare, trebuie sa considerati timpii de asteptare de la momentul respectiv (care sunt determinati de valorile initiale sau de operatiile de tipul 1 descrise in fisierul de intrare inaintea operatiei curente).

Restrictii si precizari

  • 2 ≤ N ≤ 16.000
  • 0 ≤ Ti ≤ 1.000
  • 2 ≤ M ≤ 200.000
  • Calculatoarele sunt numerotate de la 1 la N
  • In fisierul de intrare va exista cel putin o operatie de tipul 2

Exemplu

delay.indelay.out
5
1
2
3
4
5
1 2
1 3
2 4
3 5
6
2 1 4
2 3 1
1 1 100
2 1 4
2 2 4
2 2 3
7
4
106
6
105
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content