Alleib 34/100 consigli?

Aiuto
1

Ho provato a fare questo problema utilizzando 3 BFS, e calcolarmi una specie di diametro con cui trovare poi i nodi piu’ distanti ma su pochi testcase mi da wrong answer, consigli? Le prima 2 subtask giuste, 1 testcase sbagliato per ogni subtask tranne l’ultima che ne da 2.

#include <iostream>
#include <vector>
#include <queue>
#define INF 10e8

using namespace std;

vector<vector<int>> adj; //lista di adiacenza
vector<vector<int>> distances; //3 vettori per le distanze per ogni BFS

int nodi;
int distanzax;
int BFS(int start, int f) {
	vector<bool> visitati(nodi, false);
	distances[f][start] = 0;
	queue<int> q;
	int tempmax = 0, tempi = 0;
	q.push(start);
	while(!q.empty()) { //una normale BFS
		int curr = q.front();
		q.pop();
		if(visitati[curr]) continue;
		visitati[curr] = true;
		for(int i : adj[curr]) {
			distances[f][i] = min(distances[f][i], distances[f][curr] + 1);
			q.push(i);
			if(distances[f][i] > tempmax) { //qui controllo la distanza massima per salvarmela (non serve a molto, era per risparmiare tempo)
				tempmax = distances[f][i];
				tempi = i;
			}
		}
	}
	distanzax = tempmax;
	return tempi; //ritorno il nodo piu' distante
}

int build(int N, vector<int> A, vector<int> B) {
	nodi = N;
	adj.resize(N);
	distances.resize(3, vector<int>(N, INF));
	for(int i = 0; i < N - 1; ++i) { //creo la lista di adiacenza
		int from = A[i], to = B[i];
		adj[from].push_back(to);
		adj[to].push_back(from);
	}

	int n_prima_BFS = BFS(0, 0); 
	/*
	faccio la prima BFS, per vedere quale nodo e' piu' lontano
	*/
	int n_seconda_BFS = BFS(n_prima_BFS, 1); //"angolo"
	/*
	la seconda BFS per calcolarmi il "diametro" del grafo e capire quali sono i 2 nodi piu' lontani
	*/
	int n_terza_BFS = BFS(n_seconda_BFS, 2); //"altro angolo"
	/*
	la 3 serve per salvarmi le distanze dei nodi anche all'altro "angolo"
	*/
	int max = 0;
	int fin = 0;
	for(int i = 0; i < nodi; ++i) {
		if(min(distances[1][i], distances[2][i]) > max) { //controllo quale e' piu' lontano da entrambi
			max = min(distances[1][i], distances[2][i]);
			fin = i;
		}
	}
	return distances[1][fin] + distances[2][fin] + distanzax; //ritorno le distanze da *fin*, il nodo piu' lontano
}

//grader
int main() { 
	freopen("input.txt", "r", stdin);

	int n;
	cin>>n;

	vector<int> a(n - 1), b(n - 1);
	for (int i = 0; i < n - 1; ++i) {
		cin>>a[i]>>b[i];
	}

	int ans = build(n, move(a), move(b));
	cout << ans << '\n';
}
2

Ciao! In fin vorresti salvarti il nodo che massimizza distances[1][fin] + distances[2][fin], perché dovrebbe essere come massimizzare min(distances[1][fin], distances[2][fin])?

3

Ciao, grazie per la risposta. Ho immaginato che la distanza massima da un nodo al “centro” agli altri due, sara’ la distanza piu’ vicina tra i due piu’ grande possibile. Pero’ immagino ci siano dei casi specifici in cui questo non e’ vero ma non me ne vengono proprio in mente :pensive:

1 Mi Piace
4

Di nulla! Comunque questo è un controesempio:

6
0 1
1 2
2 3
3 4
3 5

In questo caso fin diventa uguale a 2, mentre dovrebbe essere 4 o 5. In effetti è già tanto che tu abbia fatto 34 ma non mi stupisco più di niente :sweat_smile:

1 Mi Piace
5

Infatti e’ strano quel punteggio, grazie di tutto :smile:

1 Mi Piace