Dessert - Aiuto

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:

#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.

Il problema (e ci ho messo un po’ a capirlo :sweat_smile:) è 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.

1 Mi Piace

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

1 Mi Piace