Aiuto per il problema Long Chain

Aiuto
1 
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 100005;
int head_[MAXN], to_[2 * MAXN], next_[2 * MAXN], edge_count = 0;
int temp_lengths[MAXN], N;

// Aggiunge un arco (u-v) alla lista di adiacenza
void add_edge(int u, int v) {
    to_[edge_count] = v;
    next_[edge_count] = head_[u];
    head_[u] = edge_count++;
}

// DFS per verificare se è possibile creare catene di lunghezza >= l
int dfs(int node, int parent, int l, int &chains) {
    int count = 0;

    for (int e = head_[node]; e != -1; e = next_[e]) {
        int child = to_[e];
        if (child == parent) continue;
        int length = dfs(child, node, l, chains);
        if (length + 1 >= l) {
            chains++;
        } else {
            temp_lengths[count++] = length + 1;
        }
    }

    // Ordina le lunghezze parziali in ordine decrescente
    sort(temp_lengths, temp_lengths + count, greater<int>());

    int i = 0;
    while (i + 1 < count) {
        if (temp_lengths[i] + temp_lengths[i + 1] >= l) {
            chains++;
            i += 2; // Accoppia due lunghezze
        } else {
            break;
        }
    }

    return (i < count ? temp_lengths[i] : 0);
}

// Verifica se possiamo creare abbastanza catene di lunghezza >= l
bool canPartition(int l) {
    int chains = 0;
    int leftover = dfs(1, -1, l, chains);

    // Deve restituire true solo se il leftover è < l
    return leftover < l;
}

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

    cin >> N;

    if (N < 100) {
        int catene[(N-1)*2];
    for(int i=0;i<(N-1)*2;i++)
        cin>>catene[i];
    int Vetduplicati[2][(N-1)*2];
    for(int i=0;i<(N-1)*2;i++)
        Vetduplicati[1][i]=0;
    int duplicati=0;
    for(int i=0;i<(N-1)*2;i++)
        for(int h=i+1;h<(N-1)*2-1;h++)
            if(catene[i]==catene[h])
            {
                int trovato=catene[i];
                bool esiste=false;
                for(int j=0;j<duplicati;j++)
                    if(Vetduplicati[0][j]==trovato)
                    {
                        Vetduplicati[1][j]++;
                        esiste=true;
                    }
                if(esiste==false)
                {
                    Vetduplicati[0][duplicati]=trovato;
                    duplicati++;
                }

            }

    int strade=1;
    for(int i=0;i<duplicati;i++)
        if(Vetduplicati[1][i]>1)
            strade+=Vetduplicati[1][i]-1;
    if(strade==0)
        cout<<N-1;
    else
    {
        cout<<(N-1)/strade;
    }
    }
    else
    {
        memset(head_, -1, sizeof(head_));

        for (int i = 0; i < N - 1; i++) {
            int u, v;
            cin >> u >> v;
            add_edge(u, v);
            add_edge(v, u);
        }

        int left = 1, right = N, result = 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (canPartition(mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        cout << result << endl;
    }

    return 0;
}

con questo codice si riesce ad fare quasi tutte le subtask1 tranne un test case qualcuno mi potrebbe aiutare ad trovare errore. Un algoritmo serve per fare i piccoli numero altro e per i grandi numeri

1 Mi Piace
3

Ciao, sembra che ci siano un po’ di idee giuste, ma purtroppo l’implementazione è davvero troppo caotica per riuscire a capire cosa stai provando a fare.

Intanto noto che stai eseguendo di fatto due programmi distinti se N < 100 e altrimenti: su quale vuoi concentrarti prima?

Dopodiché ti segnalo alcune cose per scrivere un po’ meglio che aiutano sia te sia chi ti deve aiutare:

  • Usa quello che C++ ha da offrire. Le modalità di C sono scomodissime per milioni di motivi.
    • In C++ esiste std::vector, un array dinamico di cui puoi scegliere la dimensione a tempo di esecuzione e a cui si possono aggiungere e togliere elementi. Spesso è molto più comodo di usare gli array statici di C o ancora peggio i variable length array.
      • Gli algoritmi della STL funzionano anche su std::vector, basta passare gli iteratori di inizio e fine ottenibili con i metodi .begin() e .end().
    • Le funzione di C per manipolare la memoria (tipo memset) non sono tue amiche (per esempio pensa a cosa fa memset(arr, -2, sizeof arr);.
  • Formatta appropriatamente il codice.
1 Mi Piace
4

La ringrazio ed da pochi mesi che programmo in c++ e questi consigli sono oro per me. Adesso inizio a studiare meglio come funzionano i Vector per risolvere questo problema ed i prossimi.