# Dessert - Aiuto

**URL:** <https://forum.olinfo.it/t/dessert-aiuto/6010>\
**Category:** Aiuto\
**Created:** [19 Gennaio 2020, 3:54pm UTC](https://forum.olinfo.it/t/dessert-aiuto/6010 "2020-01-19T15:54:09Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![sora\_taiga](https://forum.olinfo.it/user_avatar/forum.olinfo.it/sora_taiga/32/563_2.png) [@sora\_taiga](https://forum.olinfo.it/u/sora_taiga)\
**Post date:** [19 Gennaio 2020, 3:54pm UTC](https://forum.olinfo.it/t/dessert-aiuto/6010/1 "2020-01-19T15:54:09Z")

</div>

Buongiorno, stavo provando a risolvere dessert e mi sembrava di aver trovato una soluzione valida, tuttavia faccio solo trenta e non riesco a capire dove sia l’errore.  
Il codice e’ il seguente:

```auto
#include <assert.h>
#include <stdio.h>
#include <assert.h>
#include <queue>
#include <vector>
#include <iostream>
#include <stdlib.h>
#include <set>

 // constraints
#define MAXN 1000000

using namespace std;

// input data
int N, i, j;
int M, L[MAXN],F;

queue<int> Q;
vector<int> adj[MAXN];
int amiciOrdinato[MAXN] = {0};
int ordinato[MAXN] = {0}; // uso 0 per non ordinato, e 1 per ordinato

int main() {
	// uncomment the following lines if you want to read/write from files
	  freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	int r = 0;

	assert(1 == scanf("%d", &N));
	for (i = 0; i < N; i++) {
		assert(2 == scanf("%d %d", &M, &L[i]));
		for (j = 0; j < M; ++j) {
			assert(1 == scanf("%d", &F));
			adj[F].push_back(i);
		}
	}

	for (i = 0; i < N; i++) {
		if (L[i] == 0) {
			Q.emplace(i);
		}
	}

	while (not Q.empty()) {
		int top = Q.front();
		// se abbastanza amici hanno ordinato, ordina
		if (L[top] <= amiciOrdinato[top] && ordinato[top]==0) {
			++r;
			ordinato[top] = 1;
		}
		Q.pop();
		if (L[top] <= amiciOrdinato[top]) {
			for (int i : adj[top]) {
				if (ordinato[i] == 0) {
					// se non ha ancora ordinato
					++amiciOrdinato[i];
					Q.emplace(i);
				}
			}
		}
		
	}

	printf("%d\n", r); // print the result
	return 0;
}

```

L’idea che ho avuto è la seguente:  
Creo un vettore di adiacenza adj in cui, adj[i] è un vettore contenente gli indici di tutti quelli che ritengono i un amico. Creo poi una coda Q, un vettore amiciOrdinato, di cui amiciOrdinato[i] mi dice quanti degli amici di i hanno ordinato, e ordinato, di cui ordinato[i] mi dice se i ha ordinato (0 per no e 1 per si).  
All’inizio carico nella coda tutti quelli che hanno L=0, ossia possono ordinare subito, e per ogni persona nella coda guardo se abbastanza amici hanno ordinato, nel caso lo faccio ordinare e aumento il numero r di persone che hanno ordinato, inoltre se ordina metto nella coda tutti quelli che lo considerano amico poiché il fatto che abbia ordinato potrebbe far ordinare anche loro.

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [19 Gennaio 2020, 4:21pm UTC](https://forum.olinfo.it/t/dessert-aiuto/6010/2 "2020-01-19T16:21:12Z")

</div>

Il problema (e ci ho messo un po’ a capirlo 😅) è che se `ordinato[top]` fosse uguale a 1 giustamente non dovrebbe incrementare `r`, ma non dovrebbe nemmeno entrare nel secondo `if`, in questo modo puoi far mangiare la stessa persona più volte.

---

<div class="post-metadata">

**Author:** ![sora\_taiga](https://forum.olinfo.it/user_avatar/forum.olinfo.it/sora_taiga/32/563_2.png) [@sora\_taiga](https://forum.olinfo.it/u/sora_taiga)\
**Post date:** [19 Gennaio 2020, 4:27pm UTC](https://forum.olinfo.it/t/dessert-aiuto/6010/3 "2020-01-19T16:27:52Z")

</div>

Ahhhhhh, è vero, accidenti che svista, ora fa 100/100. Grazie mille, sarà che sono stato corrotto pur di fargli mangiare più dolci.