# Aiuto Islands IOI 2008

**URL:** <https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308>\
**Category:** Aiuto\
**Created:** [7 Ottobre 2020, 6:47am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308 "2020-10-07T06:47:37Z")\
**Posts on this page:** 18\
**Page:** 1

<div class="post-metadata">

**Author:** ![Alex0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alex0/32/736_2.png) [@Alex0](https://forum.olinfo.it/u/Alex0)\
**Post date:** [7 Ottobre 2020, 6:47am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/1 "2020-10-07T06:47:37Z")

</div>

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 ?

---

<div class="post-metadata">

**Author:** ![Alex0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alex0/32/736_2.png) [@Alex0](https://forum.olinfo.it/u/Alex0)\
**Post date:** [7 Ottobre 2020, 7:48am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/2 "2020-10-07T07:48:12Z")

</div>

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

```auto
#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;
}

```

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [7 Ottobre 2020, 8:28am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/3 "2020-10-07T08:28:01Z")

</div>

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 😉

---

<div class="post-metadata">

**Author:** ![Alex0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alex0/32/736_2.png) [@Alex0](https://forum.olinfo.it/u/Alex0)\
**Post date:** [7 Ottobre 2020, 8:31am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/4 "2020-10-07T08:31:08Z")

</div>

> [@simpatine](#):
>
> 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

avevo immaginato che la mia attuale soluzione vadi in timeout

---

<div class="post-metadata">

**Author:** ![Alex0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alex0/32/736_2.png) [@Alex0](https://forum.olinfo.it/u/Alex0)\
**Post date:** [7 Ottobre 2020, 8:32am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/5 "2020-10-07T08:32:23Z")

</div>

> [@simpatine](#):
>
> 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 KK avrà KK archi

dunque dovrei ridurre inizialmente il grafo

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [7 Ottobre 2020, 8:35am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/6 "2020-10-07T08:35:07Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Alex0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alex0/32/736_2.png) [@Alex0](https://forum.olinfo.it/u/Alex0)\
**Post date:** [7 Ottobre 2020, 8:37am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/7 "2020-10-07T08:37:17Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Alex0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alex0/32/736_2.png) [@Alex0](https://forum.olinfo.it/u/Alex0)\
**Post date:** [7 Ottobre 2020, 8:42am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/8 "2020-10-07T08:42:53Z")

</div>

> [@simpatine](#):
>
> cosa accade quando gli archi sono NN

se non erro è un cyclic graph

---

<div class="post-metadata">

**Author:** ![Alex0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alex0/32/736_2.png) [@Alex0](https://forum.olinfo.it/u/Alex0)\
**Post date:** [7 Ottobre 2020, 8:44am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/9 "2020-10-07T08:44:47Z")

</div>

piu che altro, per componenti intendi componenti fortemente connesse?

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [7 Ottobre 2020, 8:46am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/10 "2020-10-07T08:46:48Z")

</div>

Sì  
Il messaggio deve essere lungo almeno 20 caratteri

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [7 Ottobre 2020, 8:49am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/11 "2020-10-07T08:49:29Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Alex0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alex0/32/736_2.png) [@Alex0](https://forum.olinfo.it/u/Alex0)\
**Post date:** [7 Ottobre 2020, 8:54am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/12 "2020-10-07T08:54:04Z")

</div>

si intendevo quello sorry

---

<div class="post-metadata">

**Author:** ![Alex0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alex0/32/736_2.png) [@Alex0](https://forum.olinfo.it/u/Alex0)\
**Post date:** [7 Ottobre 2020, 8:56am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/13 "2020-10-07T08:56:01Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [7 Ottobre 2020, 9:43am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/14 "2020-10-07T09:43:24Z")

</div>

Eh infatti ci devi pensare un minimo 😅 sapendo che le componenti connesse sono degli **uni** cyclic 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 🙃

---

<div class="post-metadata">

**Author:** ![Alex0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alex0/32/736_2.png) [@Alex0](https://forum.olinfo.it/u/Alex0)\
**Post date:** [7 Ottobre 2020, 9:48am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/15 "2020-10-07T09:48:25Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Alex0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alex0/32/736_2.png) [@Alex0](https://forum.olinfo.it/u/Alex0)\
**Post date:** [7 Ottobre 2020, 9:50am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/16 "2020-10-07T09:50:01Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [7 Ottobre 2020, 9:53am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/17 "2020-10-07T09:53:21Z")

</div>

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).

---

<div class="post-metadata">

**Author:** ![Alex0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alex0/32/736_2.png) [@Alex0](https://forum.olinfo.it/u/Alex0)\
**Post date:** [7 Ottobre 2020, 9:55am UTC](https://forum.olinfo.it/t/aiuto-islands-ioi-2008/6308/18 "2020-10-07T09:55:55Z")

</div>

ahahah effettivamente, grazie mille