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