Ошибка перемещения

#include <stdio.h>

#define MAX 1000000

int dp[MAX];
int P[MAX], C[MAX], K[MAX], child[MAX][1000], index[MAX];
int mod = 1000000007;

void dfs(int i) {
    int j = 1;
    while (j <= index[i]) {
        dfs(child[i][j]);
        if ((C[child[i][j]] == C[i]) && (K[i] - K[child[i][j]] == 1))
            dp[i] = (dp[i] % mod + dp[child[i][j]] % mod) % mod;
        ++j;
    }
}

int main() {
    int T, N, X, i, j;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &X);

        for (i = 0; i < N; ++i)
            index[i] = 0;

        for (i = 1; i < N; ++i) {
             scanf("%d", &P[i]);
             child[P[i]][++index[P[i]]] = i;
        }
        for (i = 0; i < N; ++i)
            scanf("%d", &C[i]);
        for (i = 0; i < N; ++i) {
            scanf("%d", &K[i]);
            if (K[i])
                dp[i] = 0;
            else
                dp[i] = 1;
        }
        dfs(0);
        for (i = 0; i < N; ++i)
            printf("%d\n", dp[i]);
    }
    return 0;
}

Когда я скомпилировал приведенный выше код, я получил следующую ошибку:

In function `dfs':
(.text+0xa): relocation truncated to fit: R_X86_64_32S against symbol `index' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x3b): relocation truncated to fit: R_X86_64_32S against symbol `index' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x4f): relocation truncated to fit: R_X86_64_32S against symbol `C' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x56): relocation truncated to fit: R_X86_64_32S against symbol `C' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x60): relocation truncated to fit: R_X86_64_32S against symbol `K' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x67): relocation truncated to fit: R_X86_64_32S against symbol `K' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x74): relocation truncated to fit: R_X86_64_32S against symbol `dp' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x84): relocation truncated to fit: R_X86_64_32S against symbol `dp' defined in COMMON section in /tmp/cc0VMXET.o
(.text+0x97): relocation truncated to fit: R_X86_64_32S against symbol `dp' defined in COMMON section in /tmp/cc0VMXET.o
In function `main':
(.text.startup+0x6e): relocation truncated to fit: R_X86_64_32S against symbol `index' defined in COMMON section in /tmp/cc0VMXET.o
(.text.startup+0xba): additional relocation overflows omitted from the output
error: ld returned 1 exit status

Я знаю, что это за ошибка, как она возникает. Я искал это в stackoverflow, но не могу понять, как это исправить. Может кто-нибудь, пожалуйста, скажите мне, как исправить мой код?


c relocation
person Shanif Ansari    schedule 25.07.2017    source источник
comment
как вы компилируете? Какие аргументы? И на какой платформе? Какой компилятор?   -  person bolov    schedule 25.07.2017
comment
Я думаю, вы нарушили емкость int с переменной mod   -  person Vinay Shukla    schedule 25.07.2017
comment
@Md.RezwanulHaque По-видимому, ответ на этот вопрос, как обычно, без предупреждений.   -  person underscore_d    schedule 25.07.2017
comment
@Md.RezwanulHaque: как int mod=1000000007; выходит за пределы досягаемости? 1 миллиард подходит для 32-битного целого числа. Значение может быть неправильным для проблемы, но это не проблема диапазона.   -  person chqrlie    schedule 25.07.2017

Ответы (2)


arrow_upward
3
arrow_downward

Возможно, вы достигли предела размера глобальных переменных, определенных в вашей программе: только 2D-массив child имеет размер 4000000000 байтов (4 миллиарда байтов).

Либо уменьшите размер некоторых из этих глобальных переменных, либо выделите их из кучи во время запуска с помощью calloc().

Попробуйте эту версию, где child выделяется из кучи:

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000000

int dp[MAX], P[MAX], C[MAX], K[MAX], index[MAX];
int (*child)[1000];
int mod = 1000000007;

void dfs(int i) {
    int j = 1;
    while (j <= index[i]) {
        dfs(child[i][j]);
        if ((C[child[i][j]] == C[i]) && (K[i] - K[child[i][j]] == 1))
            dp[i] = (dp[i] % mod + dp[child[i][j]] % mod) % mod;
        ++j;
    }
}

int main(void) {
    int T, N, X, i;

    child = calloc(MAX, sizeof(*child));
    if (child == NULL) {
        fprintf(stderr, "cannot allocate child array (%llu bytes)\n",
                (unsigned long long)MAX * sizeof(*child));
        return 1;
    }

    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &X);

        for (i = 0; i < N; ++i)
            index[i] = 0;

        for (i = 1; i < N; ++i) {
            scanf("%d", &P[i]);
            child[P[i]][++index[P[i]]] = i;
        }
        for (i = 0; i < N; ++i)
            scanf("%d", &C[i]);
        for (i = 0; i < N; ++i) {
            scanf("%d", &K[i]);
            if (K[i])
                dp[i] = 0;
            else
                dp[i] = 1;
        }
        dfs(0);
        for (i = 0; i < N; ++i)
            printf("%d\n", dp[i]);
    }
    free(child);
    return 0;
}

Заметки:

  • Вы также должны проверить, совместимы ли значения, считанные из стандартного ввода, с выделенными размерами (N <= MAX и P[i] < 1000).

  • Вы можете уменьшить MAX или 1000, если выделение не удалось.

  • dp[i] = (dp[i] % mod + dp[child[i][j]] % mod) % mod; можно упростить как dp[i] = (dp[i] + dp[child[i][j]]) % mod;

person chqrlie    schedule 25.07.2017
comment
Я попытался запустить ваш код. Предыдущие проблемы были решены правильно, благодаря вам. Но теперь он дает NZEC, что является ошибкой сегментации. Пожалуйста, скажите мне, как это исправить. - person Shanif Ansari; 26.07.2017
comment
@ShanifAnsari: без тестовых данных сложно сказать - person chqrlie; 26.07.2017

arrow_upward
0
arrow_downward

Массив child состоит из 10^9 элементов, и каждый элемент имеет размер 4 байта, поэтому его размер составляет почти 4 ГБ. Однако GCC имеет ограничение на размер сегмента данных, и пороговое значение по умолчанию составляет 2 ГБ.

У вас есть два способа решить эту проблему:

  1. Уменьшить размер массива child
  2. Скомпилируйте свою программу с параметром GCC -mcmodel=medium.

Использованная литература:

http://www.network-theory.co.uk/docs/gccintro/gccintro_65.html https://gcc.gnu.org/onlinedocs/gcc-4.2.0/gcc/i386-and-x86_002d64-Options.html

person haolee    schedule 25.07.2017