/**
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/
- noi parcurgem multimea y a fiecarei reactii o singura data, in momentun in care punem in coada reactia.
Deoarece marcam in viz reactiile puse in coada noi nu vom repeta punerea in coada deci nici parcurgerealui Y
Restrictia spune ca suma vaorilor Y nu trece de 100000, deci ne incadram (nu am mai socotit parcurgerea valorilor Y la citire intrucat asta se aduna)
**/
#include <iostream>
#include <deque>
#include <vector>
#include <bitset>
using namespace std;
struct reactie {
int L;
int R;
int necunoscute;
vector<int> Y;
};
reactie e[100010];
deque<int> coada;
vector<int> Lista[100010];
int n, m, i, v, k, j, x, nod, ec, reactie, sol;
bitset<100010> f, viz;
int main () {
cin>>n>>m;
for (i=1;i<=m;i++) {
cin>>v;
f[v] = 1;
}
cin>>k;
for (i=1;i<=k;i++) {
cin>>e[i].L>>e[i].R;
e[i].necunoscute = e[i].L;
for (j=1;j<=e[i].L;j++) {
cin>>x;
Lista[x].push_back(i);
if (f[x] == 1) {
e[i].necunoscute--;
if (e[i].necunoscute == 0) {
coada.push_back(i);
viz[i] = 1;
}
}
}
for (j=1;j<=e[i].R;j++) {
cin>>x;
e[i].Y.push_back(x);
}
}
while (!coada.empty()) {
nod = coada.front();
coada.pop_front();
/// nod este o lista cu toate reactieele marcate
for (i=0;i<e[nod].Y.size();i++) {
ec = e[nod].Y[i];
if (f[ec] == 0) {
f[ec] = 1;
for (j=0;j<Lista[ec].size();j++) {
reactie = Lista[ec][j];
if (viz[reactie] == 0) {
e[reactie].necunoscute--;
if (e[reactie].necunoscute == 0) {
coada.push_back(reactie);
viz[reactie] = 1;
}
}
}
}
}
}
for (i=1;i<=100000;i++)
if (f[i] == 1)
sol++;
cout<<sol<<"\n";
for (i=1;i<=100000;i++)
if (f[i] == 1)
cout<<i<<" ";
return 0;
}
Compilation message
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++) {
~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
7696 KB |
Output is correct |
| 2 |
Correct |
73 ms |
8096 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
9080 KB |
Output is correct |
| 2 |
Correct |
141 ms |
9504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
176 ms |
10052 KB |
Output is correct |
| 2 |
Correct |
175 ms |
9568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
197 ms |
10588 KB |
Output is correct |
| 2 |
Correct |
188 ms |
10152 KB |
Output is correct |
