Ciao a tutti. Sto recentemente cercando di risolvere il problema Police investigation 2 e, essendo abbastanza nuovo dell’ambito, ho ragionato su una possibile soluzione, la quale mi sembra abbastanza realistica, ma che mi dà esito time limit exceeded in tutte i punti delle task 3, 4 e 6.
Sono abbastanza sicuro che l’errore stia nel codice, per un loop infinito o altro… ma non saprei come e dove trovarlo. Qualcuno riuscirebbe a darmi un’indizio? Grazie
// NOTE: it is recommended to use this even if you don't understand the following code.
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
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 N;
cin >> N;
int V[N];
for (int i = 0; i < N; i++)
cin >> V[i];
// insert your code here
int pos, max=0, c;
vector<int> houses, pass;
for (int i=0; i<N; i++) {
pos = i;
if (count(V, V+N, pos) > 0 && count(pass.begin(), pass.end(), pos) == 0) {
houses.clear();
c =0;
do {
pos = V[pos];
c ++;
houses.push_back(pos);
} while (pos != i && count(houses.begin(), houses.end(), pos) <=1);
if (count(houses.begin(), houses.end(), pos) <=1) {
pass.insert(pass.end(), houses.begin(), houses.end());
if (c > max) {
max = c;
}
}
}
}
cout << max << endl; // print the result
return 0;
}