Submission #143139

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
143139	2019-08-13 08:36:02	mariusnicoli	Alkemija (COCI18_alkemija)	C++14	80 / 80	197 ms	10588 KiB

alkemija

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
Structura reactie va pastra informatii despre una dintre reactiile din problema
L: cate elemente are prima multime
R: cate elemente are a doua multime
necunoscute: cate dintre cele L elemente ale primei multimi sunt deja cunoscute
(cand vor deveni cunosccute toate atunci le vom declara cunoscute pe cele R din a doua multime)
Y: vectorul cu cele R elemente ale celei de-a doua multimi, deci cele care devin automat si ele cunoscute
cand le-am aflat deja pe toate cele L din prima multime de elemente ale reactiei
In vectorul Lista tinem minte pentru fiecare element in ce reactii se afla
el in prima multime. Îl vom construi odata cu citirea reactiilor, deci nu necesita efort suplimentar
La ce il folosim? - în momentul în care un element devine cunoscut (pentru prima data - noi avem si un vector f unde f[element] = 1 daca elementul este cunoscut si 0 altfel)
vom parcurge "Lista" de reactii ale elementului respectiv si decrementam valoarea
campului "necunoscute" de la fiecare dintre ele.
Cand pentru o reactie valoarea lui "necunoscute" devine 0 inseamna ca acea
reactie ajunge sa aiba toate cele L elemente din prima sa multime cunoscute
si deci le vom face cunoscute pe cele din a doua multime
In ce ordine analizam reactiile?
- Inca dela citirea setului de elemente cuonoscute (de pe a doua linie a fisierului)
noi vom marca in f cu 1 aceste elemente.
Apoi, pentru fiecare astfel de element parcurgem "Lista" lui si decrementam campul "necunoscute"
la fiecare reactie. Dupa procesarea elementelor cunocute la inceput, sigur va fi cel putin o reactie
care le va avea cunoscute pe toate cele R din prima multime (in caz contrar nu vom mai putea obtine elemente noi).
In acest moment punem acea reactie intro-o COADA. Asadar in coada vor fi mereu
reactii care au cunoscute toate elementele primei multimi. Pe masura ce pocesam
reactiile incepand din fata cozii, vom adauga la coada pe cele la care "necunoscute ajunge 0"
Este necesar si un vector viz pentru reactii in care marcam pe cele puse deja in coada.
Pentru a analiza complexitatea, observam ca nicio parcurgere nu trece de 100000/
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

alkemija.cpp: In function 'int main()':
alkemija.cpp:86:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<e[nod].Y.size();i++) {
                  ~^~~~~~~~~~~~~~~~
alkemija.cpp:90:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (j=0;j<Lista[ec].size();j++) {
                          ~^~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8