Water park ( waterslide )


#1

Salve a tutti, per risolvere waterslide ho scritto il seguente codice

#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
class funtore
{
public:
    ///criterio : minore
    bool operator()(std::pair<int,int> primo, std::pair<int,int> secondo)
    {
    if(primo.first < primo.second)
        {
            if(secondo.first < secondo.second)
            {
                if(primo.first == secondo.first)
                    return primo.second < secondo.second;
                else
                    return primo.first < secondo.first;
            }

            else if(secondo.first > secondo.second)
            {
                if(primo.second == secondo.first)
                    return primo.first < secondo.second;
                else
                    return primo.second < secondo.first;
            }

        }
    else if(primo.first > primo.second)
        {
            if(secondo.first < secondo.second)
            {
                if(primo.first == secondo.second)
                    return primo.second < secondo.first;
                else
                    return primo.first < secondo.second;
            }

            else if(secondo.first > secondo.second)
            {
                if(primo.second == secondo.second)
                    return primo.first < secondo.second;
                else
                    return primo.second < secondo.second;
            }
        }
    }
};
int find_pool(int N, int M, int P, std::vector<int> A, std::vector<int> B)
    {
    ///il parametro N non serve
    int cont = 0;
    std::vector<int> grado(M,0);
    std::vector<float> percentuale(M,0);
    std::vector<std::pair<int,int>> valori_file;
    for(int i = 0; i < M; i++)
        valori_file.push_back(std::make_pair(A[i],B[i]));///ordinamento di A e B a coppie
    ///ordinamento rispetto al criterio del funtore
    std::sort(valori_file.begin(),valori_file.end(),funtore());
    for(int i = 0; i < M; i++)///definizioni dei gradi
        grado[A[i]]++;
    for( ; cont < M; cont++)
    if(grado[cont] == 0)///nodi con grado maggiore di 0
        break;
    percentuale[0] = 1;
    for(int i = 0; i < M; i++)///definizione percentuali
        percentuale[valori_file[i].second] += (float)(percentuale[valori_file[i].first])/grado[valori_file[i].first];
    ///individua la posizione
    int massimo = cont + 1;
    for(int i = 0; i <= P-1; i++)///massimo tra i nodi con grado 0
        if(percentuale[massimo] < percentuale[cont+i])
            massimo = cont+i;
    return massimo;
}

///ampiezza illimitata
std::vector<int> A;
std::vector<int> B;

int main() {
    FILE *fr, *fw;
    int N, M, P, i;
    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");
    fscanf(fr, "%d %d %d", &N, &M, &P);
    A.reserve(M);
    B.reserve(M);
    for(i=0; i<M; i++)
        fscanf(fr, "%d %d", &A[i], &B[i]);
    fprintf(fw, "%d\n", find_pool(N, M, P, A, B));
    fclose(fr);
    fclose(fw);
    return 0;
}

in pratica salva tutte le coppie di nodi date in input in un vector di pair<int, int>, dove vengono ordinati secondo il criterio funtore inserito(me lo ordina anche quando ho un nodo collegato a un nodo maggiore).
Poi, sempre secondo il vector di pair mi calcolo le percentuali e le salvo in un altro vector e infine trovo il maggiore. Sottoponendolo mi da sempre lo stesso errore:
Execution killed with signal 11 (could be triggered by violating memory limits).
Da cosa potrebbe derivare?


#2

La funzione reserve non è uguale alla funzione resize.
Utilizzando la funzione corretta (resize) per modificare la grandezza dei vettori “A” e “B” non ottieni più quel errore dovuto all’ accesso a memoria non allocata.
Per gli output non corretti non saprei aiutarti, non ho capito la logica che hai implementato.