Problema con "nemico mortale"


#1

Help me!
La soluzione che sottopongo alla piattaforma mi da per tutti i subtask il famigerato
“Execution killed with signal 11 (could be triggered by violating memory limits)”.
In locale è stato testato su molti casi (anche quelli della traccia ovviamente), con le assunzioni specificate nella stessa, e funziona.
Qualcuno può dare un’occhiata al codice che allego? Grazie.

/*
	Problema "Nemico mortale" OII - 2015
	Tecnica risolutiva: GRAFI (colorazione) - classificazione
	
	Per ogni componente connessa, si parte ipotizzando 2 gruppi e si assegnano i bambini ai due gruppi
	Se non sono 2 ma 3 significa che c'e' un arco in più => lo gestisco alla fine
	La strategia è opposta a quella di gestire prima il nodo iniziale
	
	Va bene anche una BFS!
*/	
#include <cstdio>
#include <cassert>
#include <cstdlib>

//---------------------------------
#include <list>

#define MAX_NODI 100000
//#define MAX_ARCHI MAX_NODI //numero di archi sono al piu' il numero di nodi

using namespace std; //necessario per utilizzare le ADT

list<int> grafo[MAX_NODI];  //orientato
//archi salvati in array di liste (LISTE DI ADIACENZA)
//ogni elemento dell'array riguarda un nodo e la lista ad esso collegata è l'elenco dei nodi ad esso adiacenti
int gruppo[MAX_NODI]; //parallelo a al vettore di liste grafo 
bool visitato[MAX_NODI];
//---------------------------------

static FILE *fr, *fw;

// Declaring variables
static int N;
static int* nemico;

// Declaring functions
void smista(int N, int* nemico);
void crea_grafo(int N);
bool presente(int k, list<int> lista);
void DFS_assegna_gruppi(int nodo);
int trova_nodi_da_visitare(int N,bool visitato[],int *nodo_iniziale_componente);
int chi_odia(int bambino);

void nuovo_gruppo();
void aggiungi(int bambino);

static int gruppi = 0;
int n_gruppi=2;
int c, n_nodi_componente;

void stampa_lista(list<int> L) {
	 list<int>::const_iterator it;
	 int n;
     for(it=L.begin(); it!=L.end(); ++it) {
    	 n = (*it);
    	 printf("%d -> ",n);
     }
     putchar('\n');
}

void smista(int N, int* nemico) {

	int n_archi; //numero inimicizie
	int n_gruppi_componente;

	//crea_grafo(N);
	int i; //,c=0;
	for (i=0; i<N; i++) {
		int u=i, v=nemico[i];
		if (!presente(v,grafo[u])) {	 	 
		 	grafo[u].push_back(v);
		}
		if (!presente(u,grafo[v])) {	 	 
		 	grafo[v].push_back(u);
		}		 	 			 	
	}
	
	//debug: visualizza lista adiacenze 
    /*printf("Lista:\n");
	for (int i=0; i<N; i++) {
		printf("%d : ",i);
		stampa_lista(grafo[i]);
		putchar('\n');
	}
	putchar('\n');	
	//================================*/
		
	int visitati=0,da_visitare;
	int nodo_iniziale_componente=0;
	do {
		c=0;
		n_nodi_componente=0;
		//attraversa componente grafo 	
		DFS_assegna_gruppi(nodo_iniziale_componente);
		n_archi=c/2;
		//calcola numero colori componente (numero gruppi)
		if (n_archi==n_nodi_componente) {//if (n_archi==N) non N globale
			if (n_nodi_componente%2==1) { //non N			
			   n_gruppi_componente=3;
			   //gruppo[nodo_iniziale_componente]=2;			   
			} else
			   n_gruppi_componente=2;			   
		} else {
			n_gruppi_componente=2;
		}
		if (n_gruppi_componente > n_gruppi) {
			n_gruppi=n_gruppi_componente;
		}
		//controlla se ci sono altre componenti (nodi da visitare)
		//se il grafo fosse connesso la DFS garantisce che li avrebbe tutti visitati 
		da_visitare=trova_nodi_da_visitare(N,visitato,&nodo_iniziale_componente);	
		visitati=N - da_visitare;
		//visitati += n_nodi_componente;
		//nodo_iniziale_componente=visitati;
	} while (visitati<N);
	
	//metto qui la generazione dell'output (per *)
	for (; gruppi<n_gruppi; ) {
		nuovo_gruppo();
		for (int b=0; b<N; b++) {			
			if (gruppo[b]==gruppi-1)
				aggiungi(b);				
		}
	}
}

//crea grafo con lista di adiacenza
void crea_grafo(int N) {
	int i; //,c=0;
	for (i=0; i<N; i++) {
		int u=i, v=nemico[i];
		if (!presente(v,grafo[u])) {	 	 
		 	grafo[u].push_back(v);
		}
		if (!presente(u,grafo[v])) {	 	 
		 	grafo[v].push_back(u);
		}		 	 			 	
	}
}

bool presente(int k, list<int> lista) {
	 list<int>::const_iterator it;
	 int n;
     for(it=lista.begin(); it!=lista.end(); ++it) {
    	 n = (*it); 
    	 if (n==k) 
    	    return true;
     }
     return false;
}

void DFS_assegna_gruppi(int nodo) {
	//marca il nodo corrente
	visitato[nodo] = true;
	n_nodi_componente++;
	// Scorre la lista di adiacenza del nodo corrente
	while(!grafo[nodo].empty()) {
		int prossimo=grafo[nodo].front();
		grafo[nodo].pop_front();
		c++;
		if (!visitato[prossimo]) {
			gruppo[prossimo]=(gruppo[nodo]+1)%2; //intanto assegna su 2 gruppi
			//se "prossimo" è adiacente a uno visitato che non è il padre "nodo" (piu precisamente, il padre non è suo nemico) 
			//significa che è l'ultimo nodo della componente connessa
			if (visitato[nemico[prossimo]]) {				
				int j=chi_odia(prossimo);				
				if (j!=-1 && nemico[prossimo]!=nodo || visitato[j]) {
					//"prossimo" è l'ultimo visitato del sottografo e chiude un CICLO
					int nodo_finale_ciclo;
					if (nemico[prossimo]!=nodo) {
						nodo_finale_ciclo=nemico[prossimo];
					} else {
						nodo_finale_ciclo=j;
					}
					//Controllo se per combinazione (vedi casi particolari foglio) i due nodi hanno stesso gruppo
					//se diverso ok, lascio l'ultimo nodo nel gruppo assrgnato dalla DFS
					//altriementi l'unico modo è assegnarlo al terzo gruppo					
					if (gruppo[prossimo]==gruppo[nodo_finale_ciclo]) {
						gruppo[prossimo]=2; //terzo gruppo											
					} 
				} 
			} 			
			//visitato[prossimo]=true;
			DFS_assegna_gruppi(prossimo);		
		}
	}
}

//-1 se nessuno lo odia
int chi_odia(int bambino) {
	int k=-1;
	for (int i=0; i<N; i++) 
		if (nemico[i]==bambino) 
			k=i;
	return k;
}

int trova_nodi_da_visitare(int N,bool visitato[],int *nodo_iniziale_componente) {
	int c=0,k=-1;
	for (int i=0; i<N; i++) {
		if (!visitato[i]) {
			if (k==-1)
			    k=i;
			c++;
		}
	}
	(*nodo_iniziale_componente)=k;
	return c;
}

void nuovo_gruppo() {
	//if (gruppi != 0) fprintf(fw, "\n");
	if (gruppi != 0) fprintf(stdout, "\n");
	gruppi++;
}

void aggiungi(int bambino) {
	//fprintf(fw, "%d ", bambino);
	fprintf(stdout, "%d ", bambino);
}

int main() {
	//#ifdef EVAL
		fr = fopen("input.txt", "r");
		fw = fopen("output.txt", "w");
	//#else
	//	fr = stdin;
	//	fw = stdout;
	//#endif

	// Reading input
	fscanf(fr, "%d ", &N);
	nemico = (int*)malloc(N * sizeof(int));
	for (int i0 = 0; i0 < N; i0++) {
		fscanf(fr, "%d ", &nemico[i0]);
	}

	// Calling functions
	smista(N, nemico);

	fclose(fr);
	fclose(fw);
	return 0;
}

#2

Guardando il tuo codice vedo che il main e il grader sono in un unico file. Prima di risolvere il problema dovresti capire come funziona il grader e come si usa. Puoi guardare questo post.

Nello specifico ciò che accade quando viene valutato sul server è:

  • Nel grader vengono dichiarate le variabili N e nemico come statiche pertanto vengono “viste” solo dal grader e non sono accessibili dalla tua soluzione.
  • Nella tua soluzione dichiari delle variabili globali con il nome N e nemico senza però inizializzare.
  • All’interno della funzione smista vengono passati come parametri altre variabili con il nome N e nemico che vanno ad “oscurare” le variabili dichiarate globalmente nella tua soluzione.
  • Viene chiamata la funzione DFS_assegna_gruppi che tenta di accedere all’array nemico che però non è mai stato inizializzato e pertanto il programma va in segmentation fault.