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
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
se non erro è un cyclic graph
piu che altro, per componenti intendi componenti fortemente connesse?
Sì
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 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
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).
ahahah effettivamente, grazie mille