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;
}