Oggi mi ritrovo davanti al problema depura. Utilizzando la soluzione illustrata nel libro di bugatti, l’algoritmo fa 89.47/100 perché va in timeout nei testcase 9 e 16. Pure utilizzando un vettore con valori booleani invece di un set (quindi rendendo la ricerca costante, invece di logaritmica), il mio programma fa comunque 89.47/100
Questo è il mio codice.
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define MAXK_R 1001
#define MAX_A 2001
using namespace std;
int K;
int R;
bool inAcqua[MAX_A] = { 0 };
list<int> connected[MAX_A];
int added = 0;
bool solve(int node) {
if (inAcqua[node] == true) return true;
bool verified = true;
for (list<int>::iterator x = connected[node].begin(); x != connected[node].end(); x++) {
if (connected[*x].size() == 0 && inAcqua[*x] == false) return false;
verified *= solve(*x);
}
if (verified) {
added++;
inAcqua[node] = true;
}
return verified;
}
int main() {
ifstream cin("input.txt");
ofstream cout("output.txt");
cin >> K >> R;
for (int i = 1; i <= K; i++) {
int tmp;
cin >> tmp;
inAcqua[tmp] = true;
}
for (int i = 1; i <= R; i++) {
int tmp;
cin >> tmp;
int n;
cin >> n;
for (int j = 0; j < n; j++) {
int tmp2;
cin >> tmp2;
connected[tmp].push_back(tmp2);
}
}
if (solve(1)) {
cout << added << endl;
} else {
cout << -1 << endl;
}
}
