Problema Convoglio?

Aiuto
1

Sto cercando di risolvere il problema Convoglio, ma continuo a ricevere lo stesso errore su tutti i subtask tranne il primo: “Il matching è lo stesso”.

Il codice usa una funzione ricorsiva per fare backtracking, e una volta raggiunto l’ultimo elemento (depth == n) controlla (check()) che la soluzione generata sia diversa da quella fornita da Turing (una volta arrivato a questo punto è garantito che la soluzione sia valida, ovvero ogni associazione è univoca).

Inoltre, ho provato a sottomettere una soluzione che stampi direttamente la soluzione di Turing, il che dovrebbe portare all’errore “Il matching è lo stesso” per tutti i subtask, ma questo avviene solo per il primo, mentre per gli altri risulta “Mancano degli archi.”. Per cui, sono io ad essere fuso o è un problema più grande?

2

Iniziamo con :

Inviando semplicemente un codice che legge solo la corrispondenza e la stampa, si ottiene l’ errore " Il matching è lo stesso. "
codice :

#include <bits/stdc++.h>

using namespace std;

#define MAXN 100000

pair <int,int> v[MAXN];
int N,M;
int main(){
	ifstream fin ("input.txt");
	ofstream fout ("output.txt");
	fin >> N >> M;
	for(int i = 0; i < N; i++){
		fin >> v[i].first >> v[i].second;
		fout << v[i].first << " " << v[i].second << "\n";
	}
}

immagine

Sostituendo nella lettura turing[i] = b con turing[a] = b il tuo codice sembra rispondere bene ma ottieni timeout totalizzando 21 / 100.

3

Ecco il problema, grazie mille.
Ora vedo di trovare una soluzione più efficiente, ma almeno mi sono tolto di mezzo questa cosa.