Aiuto Islands IOI 2008

Sto cercando una soluzione per islands.
L’idea è che sommo la strada massima che riesco a percorrere in ogni grafo (sono più grafi disconnessi) e avevo in mente una soluzione O(N(N+M)) per ogni grafo (dfs N volte per trovare il più lungo percorso e avrei identificato i diversi grafi tramite bfs)
qualche hint @simpatine @v.bizzarri ?

questa soluzione come mi aspettavo va in Execution timed out (attuale punteggio 51.52 / 100 )
qualche hint?
soluzione attuale:

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#define MAXN 1000001

using namespace std;

vector<vector<pair<long long,long long>>>V(MAXN);
vector<long long>D(MAXN);
queue<long long>q;
vector<bool>vis(MAXN);
vector<bool>graph(MAXN);

long long dfs(long long node,long long d){

	if(vis[node])
		return-1;
	
	vis[node]=true;
	D[node]=max(D[node],d);
	
	for(auto i:V[node])
		d=max(d,dfs(i.first,D[node]+i.second));
	
	D[node]=0;
	vis[node]=false;
	return d;
}

int main()
{

//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);

	long long N,sol=0;
	cin>>N;
	
	for(int i=0;i<N;i++){
		long long x,l;
		cin>>x>>l;
		V[i].push_back({x-1,l});
		V[x-1].push_back({i,l});
	}
	
	for(long long start=0;start<N;start++){
		long long mx=0;
		if(!graph[start]){
			q.push(start);
			
			while(!q.empty()){
				auto i=q.front();
				q.pop();
				if(!graph[i]){
					graph[i]=true;
					for(auto a:V[i])
						q.push(a.first);
					
					mx=max(mx,dfs(i,0));
				}
			}
			sol+=mx;
		}
	}
	cout<<sol;
	
	return 0;
}


Ciao! Con questo approccio non andrai molto lontano, il problema è che funziona con qualsiasi grafo generico (almeno credo), mentre le assunzioni dell’esercizio sono molto più forti, devi quindi ragionare su quelle.
Immagino tu sappia che un grafo connesso con N-1 archi è un albero, cosa accade quando gli archi sono N?
Ok che nel problema il grafo non è per forza connesso, ma dato che da ogni nodo parte uno e un solo arco ogni componente connessa di grandezza K avrà K archi, quindi rispondendo alla domanda di prima saprai come sono fatte tutte le componenti connesse, poi potrai pensare alla soluzione.
Spero di essere stato claro :wink:

avevo immaginato che la mia attuale soluzione vadi in timeout

dunque dovrei ridurre inizialmente il grafo

Sì sicuramente può aiutarti, alla fine la risposta è la somma sulle componenti. Ovviamente però alle IOI devono confonderti per forza, quindi un grafo connesso gli suonava troppo easy.

ci provo xD grazie mille
nel caso in cui abbia problemi scusa ma ti disturberò xD

1 Mi Piace

se non erro è un cyclic graph

piu che altro, per componenti intendi componenti fortemente connesse?


Il messaggio deve essere lungo almeno 20 caratteri

Cioè del grafo non orientato insomma, non so bene che intendi.

si intendevo quello sorry

più che altro trovando le componenti riesco sicuramente a ridurre il grafo ma non saprei esattamente come usarle per trovare direttamente il percorso più lungo

Eh infatti ci devi pensare un minimo :sweat_smile: sapendo che le componenti connesse sono degli unicyclic graphs.
Se poi non ci riesci subito non preoccuparti, è un problema per niente banale. Personalmente penso che sia meglio avere dei problemi irrisolti da riguardare in seguito piuttosto che farsi guidare completamente alla soluzione, è molto più costruttivo arrivarci da solo anche dopo mesi passati a risolvere problemi più abbordabili, per questo al massimo ti darò qualche hint o qualche aiuto con il debug del codice.
Poi non so esattamente quanti problemi delle IOI hai risolto, se è il tuo primo (o se in generale sei all’inizio) meglio prendersi tutto il tempo necessario, poi fa come ti pare eh :upside_down_face:

ahaha grazie mille vedo che riesco a fare, ovvio che se richiede più conoscenze di quante ne abbia cerco di apprenderle se possibile, ma nel caso in cui non riesca a risolverla la risolverò in futuro.
Attualmente mi sto esercitando sui grafi per le regionali anche se credo (spero) di saper risolvere i problemi sui grafi con la difficoltà delle territoriali

dovrei esercitarmi piuttosto su dp che è un po’ una mia carenza, nel caso qualche consiglio per migliorare/ esercizi da fare?

Sì sai com’è, dato che non siamo in Cina per le territoriali non serve risolvere esercizi delle internazionali (se sai risolverli tanto meglio).
Di esercizi dp ne trovi a valangate ovunque, cioè puoi cercare il tag su CMS o su codeforces e sei apposto (ah ovviamente il consiglio per migliorare è fare esercizi).

1 Mi Piace

ahahah effettivamente, grazie mille

1 Mi Piace