Salve a tutti,
Mentre cercavo di risolvere questo problema, ho notato che il mio codice evitava di visitare alcuni nodi, soprattutto nel subtask 2 che prevede che ogni relazione sia simmetrica. Non ho ben capito la differenza tra il task 2 e il 3, se un bambino può avere al più un nemico e ogni bambino deve averne almeno 1, le relazioni non devono essere simmetriche? 
Me lo domando perché l’intero task 3 è stato risolto dal mio codice iniziale, mentre solo per gli ultimi 2 test del task 2 è stato lo stesso, per gli altri portava output malformato : bambini mancanti. Non ho trovato l’errore, ma ho scritto due righe di codice alla fine che aggiustano tutto alla meno peggio. Sono passato da 34 a 73 punti in questo modo, solo gli ultimi 3 test del task 5 vanno in time out.
Essendo 0.5 il limite di tempo di questo problema non credo che riuscirei mai ad uscire dal time out, ma sono curioso di capire perché alcuni nodi non sono stati visitati. Questo è il mio codice:
#include <vector>
using namespace std;
struct n{int c;vector <int> g;
n (): c(-1),g(){}
};
int gruppi=0;
int N;
int nemico[100000] ;
void nuovo_gruppo();
void aggiungi(int bambino);
void smista(int N,int* nemico)
{n V[N];
int t,f,a,temp,ng=2,j;
for(t=0;t<N;t++)
{a=nemico[t];
V[a].g.push_back(t);
V[t].g.push_back(a);
}
bool s[N];
vector <int> pila;
for(f=0;f<N;f++)
{if(s[f]==false)
{pila.push_back(f);
while(!pila.empty())
{temp=pila[0];
pila.erase(pila.begin());
s[temp]=true;
if(V[temp].c==-1)
V[temp].c=0;
for(t=0;t<V[temp].g.size();t++)
{if(V[V[temp].g[t]].c==-1)
{if(V[temp].c==0)
V[V[temp].g[t]].c=1;
else V[V[temp].g[t]].c=0;
pila.push_back(V[temp].g[t]);
}
else if(V[temp].c==V[V[temp].g[t]].c)
{V[V[temp].g[t]].c=2;
ng=3;
}
}
}
}
}
a=0;
for(t=0;t<ng;t++)
{nuovo_gruppo();
for(j=0;j<N;j++){
if(V[j].c==t)
{aggiungi(j);
}
if(V[j].c==-1)
{if(V[nemico[j]].c==0)
V[j].c=1;
else {V[j].c=0; aggiungi(j);}}
}
}
}
P.S: mi piacerebbe sapere cosa c’è nel test 12 subtask 3, ha N=100000 e mi ha dato una soluzione subottima mentre sperimentavo 