SIGSEGV __gnu_cxx :: new_allocator <int>:: конструкция в Codeforces Round # 660 Задача D - PullRequest
Новая
       126

SIGSEGV __gnu_cxx :: new_allocator <int>:: конструкция в Codeforces Round # 660 Задача D

0 голосов
/ 04 августа 2020

Я работал над проблемой из раунда CodeForces # 660 Проблема D

Мой код выглядит следующим образом: 

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> child; //Array of b[i](parent) vs i(child)
vector<long long int> a; //We will update it later, and will be our subtree
vector<int> b,found;


void DFS(int index_ptr ,int *answer){
    if(found[index_ptr] == 0){
        found[index_ptr] = 1;

        //Call childor
        for(int i=0;i<child[index_ptr].size();i++){
            DFS(child[index_ptr][i], answer);
        }

        //As we are traversing back just add the answer
        *answer += a[index_ptr];
        if(a[index_ptr] > 0){
            a[b[index_ptr]] += a[index_ptr];
        }
    }
    return;
}

int main()
{ 
    int n,i,answer;
    cin >> n;   
    a.clear();  
    a.resize(n);
    b.clear();
    b.resize(n);
    found.clear();
    found.resize(n);

    for(i=0;i<n;i++){
        cin >> a[i];
        found[i] = 0;
    }

    vector<int> parent;
    for(i=0;i<n;i++){
        cin >> b[i]; 
        if(b[i]==-1)
            parent.push_back(i);
    }

    child.clear();
    child.resize(n);
    for (i=0;i<n;i++){
        child[b[i]].push_back(i);
    } 
    
    for(i=0;i<parent.size();i++){
        DFS(i, &answer);
    }
    
    cout << answer << endl;
    return 0;
}

Но он возвращает ошибку сегментации

После запуска gdb он показывает следующие результаты: 

Breakpoint 3, main () at flintTreasure_V2.cpp:54
54          child[b[i]].push_back(i);
(gdb) c
Continuing.

Program received signal SIGSEGV, Segmentation fault.
0x000055555555692d in __gnu_cxx::new_allocator<int>::construct<int, int const&>
    (this=0x55555576e368, __p=0x4)
    at /usr/include/c++/7/ext/new_allocator.h:136
136     { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }

Я скомпилировал его с тегом -Wall, и он не показал никаких предупреждений, о которых я должен беспокоиться

Я никогда раньше не сталкивался с этим типом ошибки сегментации, я думаю, это как-то связано с моим векторным распределением или использованием

1 Ответ

0 голосов
/ 04 августа 2020

В качестве общего ответа: вы не выполняете никаких явных выделений или удалений, поэтому, скорее всего, проблема связана с доступом за пределы одного из векторов. Если вы используете v.at(i) вместо v[i] для доступа к i-му элементу вектора v, доступ за пределы будет вызывать исключение, а не вызывать ошибку сегментации (или хуже).

Точнее, к этому коду: вы обращаетесь к вектору в пределах child по индексу b[i], но раньше кажется, что b[i]==-1 является допустимым или ожидаемым вводом. Я предполагаю, что, не видя входных данных, вы пытаетесь вернуть sh значение вектора в child[-1], что является выходом за границы.

...