Appetito aracnide 70/100

I 3 casi sbagliati che non mi fanno raggiungere il 100/100 mi danno come errore Execution killed with signal 11 e nodo non esistente, onestamente non ho idea di dove avvengono questi problemi nel mio programma (soprattutto il secondo) vi allego il programma potreste darmi una mano?

#include <bits/stdc++.h>
#define MAXN 100
using namespace std;
vector<int> adj[MAXN];
int check=0;
int N,M;
int r;
int sol[100000];
void DFS(int s, int n){ //s nodo , ed n indice del vettore sol
	if(check) return; //check lo uso per controllare se ha trovato soluzione
	r=n; //r invece lo uso per sapere quanto è lungo il vettore sol
	sol[n]=s; //il vettore segna i nodi su cui il programma passa
	if(sol[n-2]==sol[n] && n>=2){ //controlla che se nel cercare una strada entra in un ciclo
//ad esempio ha come strada 0 6 3 6, returna se il nodo 3 aveva un altra strada, altrimenti
// era costretto a passar di li perciò continua
		if(adj[sol[n-1]].size()!=1) return;
		 
	}
	if(n%2==0){ //se sol ha un numero pari di nodi controlla se il nodo attuale
// è direttamente collegato alla soluzione, ed in tal caso imposta check=1 in modo da 
//uscire dalla funzione
		for(int i=0;i<adj[s].size();i++){
			if(adj[s][i]==0){
				check=1;
				return;
			}
		}
	}
	n++; 
	for(int i=0;i<adj[s].size();i++){
		if(adj[s][i]!=0)	DFS(adj[s][i],n); //va su un altro nodo che non sia 0
	}
}

int main(void)
{
	FILE *fr, *fw;
    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");
	int i,a,b;
	assert(2 == fscanf(fr, "%d%d", &N, &M));
	for(i=0;i<M;i++){
		assert(2 == fscanf(fr, "%d%d", &a, &b));
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	sol[0]=0; 
	for(i=0;i<adj[0].size() && check==0;i++){
		DFS(adj[0][i],1); //per ogni nodo collegato a 0 controlla se
// è possibile raggiungere una soluzione, 1 è l'indice di dove iniziare a salvare il percorso nel vettore sol
	}
	fprintf(fw, "%d\n", r+1);
	for(i=0;i<=r;i++){
		fprintf(fw, "%d ", sol[i]);
	}
	fprintf(fw, "0 ");
return 0;
}

Ci sono vari topic su ‚ÄúAppetito Aracnide‚ÄĚ ad esempio:

Appetito aracnide (tecla)

Ho cambiato il programma vedendo sia da ci√≤ che mi hai mandato sia da altre richieste sullo stesso problema (soprattutto questo Aiuto Appetito aracnide (tecla) - n¬į13 da Alex0 ), per√≤ continua a darmi 3 errori (su casi diversi ora) dicendo che i nodi non esistano, continuo a non capirne il motivo essendo che gli unici valori che il mio vettore soluzione prende sono da adj e da valori gi√† presenti nel vettore. Hai qualche idea di cosa possa causarmi questo problema?

#include <bits/stdc++.h>
#define MAXN 31
using namespace std;
vector<int> adj[MAXN];
int check=0;
int N,M;
int r;
int vis[MAXN];
int sol[200000];

void DFS(int s,int n){
	if(check==1) return;
	r=n;
	sol[n]=s;
	if(sol[n-2]==sol[n] && n>=2){
		if(adj[sol[n-1]].size()!=1) return;
	}
	if(vis[s]!=0){ //controlla se il nodo è gia stato visitato
		if((n-vis[s]+1)%2==0){ //in caso lo sia controlla se c'è un numero
//pari di nodi su cui si è passati tra i due nodi in questione, se c'è
			check=1; //imposta check =1 per uscire dalle funzioni
			int u=n+1; //u e c scriveranno copieranno tutti i nodi già visitati
// da indice n fino a 0 del vettore sol 
			int c=vis[s]-1;
			for(;c>=0;u++,c--){
				sol[u]=sol[c];
				r++; //r tiene conto di quante celle è composto sol
			}
			return;
		}
	}
	vis[s]=n;

	for(int i=0;i<adj[s].size();i++){
		if(adj[s][i]!=0)	DFS(adj[s][i],n+1);
	}
	
}

int main(void)
{ //la parte del main non l'ho modificata
	FILE *fr, *fw;
    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");
	int i,a,b;
	assert(2 == fscanf(fr, "%d%d", &N, &M));
	for(i=0;i<M;i++){
		assert(2 == fscanf(fr, "%d%d", &a, &b));
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	sol[0]=0;
	for(i=0;i<adj[0].size() && check==0;i++){
		DFS(adj[0][i],1);
	}
	fprintf(fw, "%d\n", r);
	for(i=0;i<=r;i++){
		
		fprintf(fw, "%d ", sol[i]);
	}
return 0;
}

p.s. facendo un po di esperimenti ho scoperto che il problema non è nella funzione DFS, cioè nel vettore sol i valori maggiori di N non vengono dati all’interno della funzione ma da qualche altra parte, non ho idea del perchè ma aggiungendo:

if(sol[i]>=N) sol[i]=adj[sol[i-1]][0];

dopo le assegnazioni nella funzione (cioè sol[n]=s e poi a sol[u]=sol[c]), mi continua a dire che il nodo non è esistente, ma se lo aggiungessi prima del printf, arrivo a 80/100 e giustamente mi dice che non esiste il filamento agli altri due casi (il valore adj[sol[i-1]][0] è solo per dare sicuramente un nodo esistente, è ovvio il fatto che sia poco probabile che tale nodo abbia un collegamento con sol[i-1] e sol[i+1]).

Questo funziona ma è modificato abbastanza, (con poche modifiche faceva 90):

#include <bits/stdc++.h>
#pragma GCC optimize ("O3") 
#pragma GCC optimization ("unroll-loops")
#define MAXN 31
using namespace std;
vector<int> adj[MAXN];
int check = 0;
int N, M;
int r;
int vis[MAXN];
int sol[200000];

void DFS(int s, int n,int prec) {
    if (check == 1) return;
    r = n;
    sol[n] = s;
    if (n >= 2 && sol[n - 2] == sol[n] ) {
        if (adj[sol[n - 1]].size() != 1) return;
    }
    if (vis[s] != 0) { //controlla se il nodo è gia stato visitato
        if ((n - vis[s] + 1) % 2 == 0) { //in caso lo sia controlla se c'è un numero
//pari di nodi su cui si è passati tra i due nodi in questione, se c'è
            check = 1; //imposta check =1 per uscire dalle funzioni
            int u = n + 1; //u e c scriveranno copieranno tutti i nodi già visitati
// da indice n fino a 0 del vettore sol 
            int c = vis[s] - 1;
            for (; c >= 0; u++, c--) {
                sol[u] = sol[c];
                r++; //r tiene conto di quante celle è composto sol
            }
        }
        return;  // che il loop sia valido o no torniamo indietro      
    }
    vis[s] = n;
    for (int i = 0; i < adj[s].size(); i++) {
        if (adj[s][i] !=prec) {
            DFS(adj[s][i], n + 1, s);
        }       
    }
}

int main(void)
{ //la parte del main  modificata
    FILE* fr, * fw;
    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");
    int i, a, b;
    fscanf(fr, "%d%d", &N, &M);
    for (i = 0; i < M; i++) {
        fscanf(fr, "%d%d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    DFS(0, 0,-1);
    fprintf(fw, "%d\n", r);
    for (i = 0; i <= r; i++) {
        fprintf(fw, "%d ", sol[i]);
    }
    return 0;
}
1 Mi Piace

Grazie, non mi sembra comunque modificato molto, con questa modifica posso anche togliere i due if sotto sol[n]=s; perchè era ciò che facevano, comunque volevo chiederti cosa fanno quei due #pragma

Si puoi togliere quei due if; i due #pragma servono per velocizzare l’esecuzione ma qui servono a ben poco vista l’esiguità dei dati da elaborare.

1 Mi Piace

Per essere pignoli e non fidarsi dei testcase deboli prova con questo input:
3 3
0 1
1 2
2 0
e risistema le cose.

1 Mi Piace