Fişierul intrare/ieşire:tabara2.in, tabara2.outSursă.com 2009, Runda 1
AutorRadu ZernoveanuAdăugată deraduzerRadu Zernoveanu raduzer
Timp execuţie pe test0.15 secLimită de memorie80192 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tabara2

Alexandra isi petrece vacanta de vara intr-o tabara, in care participantii au fost impartiti in echipe, iar ea a fost aleasa lider al uneia dintre ele. Echipele trec prin diferite probe in urma carora acumuleaza puncte, echipa cu cele mai multe puncte castigand trofeul taberei.

Pentru prima proba, fiecare echipa a primit o harta a taberei pe care sunt marcate N locatii, numerotate de la 1 la N si o lista de sarcini numerotate de la 1 la S, fiecare sarcina valorand un anumit numar de puncte. Sarcinile vor fi realizate tinand cont de instructiunile primite de la organizatori pe tot parcursul probei. Instructiunile sunt de 2 tipuri:

1) Realizarea sarcinii i permite realizarea sarcinii j si invers (realizarea sarcinii j permite realizarea sarcinii i).
2) La locatia i poate fi realizata sarcina j (dupa care pot fi realizate sarcinile permise de instructiunea 1).

Cerinta

Ajutati-o pe Alexandra ca pentru locatiile i si j date sa realizeze sarcina cu punctaj maxim pe care o poate indeplini plecand din orice locatie din intervalul [i, j].

Date de intrare

Pe prima linie a fisierului de intrare tabara.in se gasesc 3 numere N, S si M reprezentand numarul de locatii, numarul de sarcini si, respectiv, numarul de instructiuni si cerinte. Pe a doua linie se afla S numere semnificand punctajul sarcinilor in ordine, de la 1 la S. Pe urmatoarele M linii vor fi date instructiunile si cerintele. O linie va fi de forma:

1) U 1 i j -> Realizarea sarcinii i permite realizarea sarcinii j si invers (realizarea sarcinii j permite realizarea sarcinii i).
2) U 2 i j -> La locatia i poate fi realizata sarcina j (dupa care pot fi realizate sarcinile permise de instructiunea 1).
3) Q i j -> Sa se afiseze in fiesierul de iesire sarcina cu punctaj maxim pe care o poate realiza dintr-o locatie k, ikj.

Date de ieşire

In fisierul de iesire tabara.out, pentru fiecare cerinta 'Q' se va afisa numarul cerut pe cate o linie.

Restricţii si precizari

  • 1 ≤ N, S, M ≤ 50 000
  • Pentru 30% din teste 1 ≤ N, S, M ≤ 1 000
  • Atentie! Se garanteaza ca o sarcina poate fi indeplinita numai dintr-o locatie (direct sau indirect).
  • Punctajul unei sarcini este ≤ 1 000 000 000.

Exemplu

tabara2.intabara2.out
2 4 6
3 2 4 1
U 1 2 4
U 2 1 1
U 2 2 2
Q 1 2
U 1 3 4
Q 1 2
3
4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content