zadanie Midas XXIV OI, process exited due signal 11

Question

Napisałem kod do zadania: https://szkopul.edu.pl/problemset/problem/wrTmzO9-dzEbLtsRUCdMV2_W/site/?key=statement . Dla przykładowego testu program odpalany u mnie (w CodeBlocks) działa i zwraca poprawny wynik lecz gdy wysyłam go do sprawdzenia dostaję komunikat process exited due to signal 11, a czasami signal 6. Wiem, że oznacza to, że wychodzę poza zakres tablicy ale nie mogę zlokalizować błędu.

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 7;

vector <int> G[MAXN];
queue <int> q;
bool lewy[MAXN];
bool visited[MAXN];

double long odl[MAXN];

int BFS(int v)
{
    q.push(v);
    visited[v] = 1;
    while(!q.empty())
    {
        v = q.front();
        q.pop();
        for (int i = 0; i < G[v].size(); i++)
        {
            int u = G[v][i]; 
            if (!visited[u])
            {
                if(lewy[u])  odl[u] = odl[v]*2;
                else         odl[u] = (odl[v]*2) + 1;
                q.push(u);  visited[u] = 1;
            }
        }
    }
}

int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, z;
    int x, y;
    odl[1] = 0;

    cin >> n;

        cin >> x >> y;
        G[1].push_back(x);
        G[1].push_back(y);

        odl[x] = 0; lewy[x] = 1;
        odl[y] = 1;


    for(int i = 2; i <= n; i++)
    {
        cin >> x >> y;
        if(x) G[i].push_back(x);
        if(y) G[i].push_back(y);
        lewy[x] = 1;
    }
    BFS(1);

    cin >> z;

    for(int i = 0; i < z; i++)
    {
        cin >> x >> y;

        if(odl[x] >= odl[y]) cout<<"TAK\n";
        else cout << "NIE\n";
    }
    return 0;
}

 

Comments

Jakby co, to zadanie nie jest publiczne.

Wiem, że oznacza to, że wychodzę poza zakres tablicy ale nie mogę zlokalizować błędu.

Odpal w debuggerze lub np z AddressSanitizerem włączonym?

BTW, te stałe wielkie globalne tablice na pewno nie ułatwiają.

---

Sorry, już poprawiłem linka. Jak już pisałem program odpalony w CodeBlocksie działa i debuggowanie w niczym nie pomogło. Co do tych globalnych tablic, co sugerujesz, bo ograniczenia zadania są do n <= 1'000'000 więc tą pamięć i tak muszę zarezerwować

Answer 1

Kiedy przesyłasz gotowe rozwiązanie to są wykonywane testy czy przechodzi wszystkie przypadki i jeżeli przekroczy limit czsasu to następuje przerwanie wykonywania programu SIGABRT (signal 6), a jak przekroczysz limit pamięci i odwołujesz się do pamięci do której nie masz dostępu to leci SIGSEGV (signal 11).

Patrząc po twoim kodzie program ma porządny problem z pamięcią (jak dobrze policzyłem alokując statycznie pamięć, dla skrajnego przypadku potrzebujesz około 4TB pamięci operacyjnej) i nie masz pojęcia o drzewach binarnych.

Po pierwsze zapoznaj się z drzewami binarnymi, ponieważ mocno to ci pomoże w optymalizacji czasowej i pamięciowej tego kodu.

Porady:
1. Tablicę vector'ów zastąp tablicą dynamiczną elementów drzewa (rodzic, lewe i prawe dziecko oraz jego wartość itp)
2. Zamiast statycznie alokowanych tablic wykorzystaj dynamicznie alokowane, które będą mieć rozmiar ilości elementów, a nie zawsze maksymalnej wartości

Comments

Rozważałem użycie drzewa binarnego ale stwierdziłem, że nie jest to konieczne do zrobienia tego zadania, więc z niego zrezygnowałem. Nie rozumiem co zajmuje aż  tyle pamięci, ponieważ milion double long'ow zajmuje około 0,01 GB (jeden double long 12 bajtow). Zastanawia mnie też co dałoby dynamiczne alokowanie pamięci skoro w skrajnym przypadku n = 1 000 000 również będę potrzebował tyle samo pamięci co rezerwując ją statycznie, chyba, że czegoś nie rozumiem. Co do tych sygnałów, dlaczego wyrzuca mi "błąd wykonania" i signal 6 zamiast "przekroczono limit czasu" oraz  signal 11 zamiast "przekroczono limit pamięci". Czym to się różni?