配列が大きくなりすぎる

Question

質問内容

以下のリンクの問題を解いていたのですが，自分のやり方では配列が大きくなりすぎてしまってコンパイルが出来ない状態です．
小さくするには二次元から一次元に変えればいいのではと思ったのですが，記憶して後で使用しているのでそれもできませんでした．どのようにすれば小さい配列に落とし込むことが出来るのか教えてください．
問題

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

#define A 100000

int reach[A][A]

int main(void){
    int numdesk,numroad;

    scanf("%d %d",&numdesk,&numroad);

    int *height,**road;

    height=(int *)malloc(sizeof(int)*numdesk);

    for(int i=0;i<numdesk;i++) scanf("%d",height[i]);

    road=(int **)malloc(sizeof(int *)*numroad);
    for(int i=0;i<numroad;i++) road[i]=(int *)malloc(sizeof(int)*2);


    for(int i=0;i<A;i++){
        for(int j=0;j<A;j++) reach[i][j]=0;
    }
    int num[A]={0};

    for(int i=0;i<numroad;i++){
        scanf("%d %d",road[i][0],&road[i][1]);
        reach[road[i][0]][num[road[i][0]]]=road[i][1];
        reach[road[i][1]][num[road[i][1]]]=road[i][0];
    }

    int maxID[A]={0};
    int maxH=0;
    int flag[A]={0};

    for(int i=0;i<numdesk;i++){
        int k=0;
        maxID[i]=i+1;
        maxH=height[i];
        while(reach[i][k]!=0){
            if(height[reach[i][k]]>maxH) {
                maxH=height[reach[i][k]];
                maxID[i]=reach[i][k];
            }
            k++;
        }
        flag[maxID[i]]=1;
    }

    int count=0;
    
    for(int i=0;i<numdesk;i++){
        count+=flag[i];
    }

    printf("%d\n",count);


    return 0;
}

Comments

[cateye]

そもそも何をしようとしていますか？
「最短経路問題」の距離を標高として考えましょう。

[mjk]

公式解説にヒントと解答例ありますよ。
https://img.atcoder.jp/abc166/editorial.pdf

[ttyp03]

そもそもreach定義行にセミコロンがついていないのですが、それを配列が大きくてエラーになっていると勘違いしていないでしょうか？
まあ配列が大きくなるのは改善すべきですが。

[退会済みユーザー]

セミコロンを付ければコンパイル通りますね。
まあRuntime errorになりますが

なぜ自分がN*N個の配列を作ろうと思ったかをよく考えなおしてみましょう

この問題はN個の標高とN個の最大値の情報を持ちたいので、
N+N個の情報があれば解ける、という事が理解できているかということを問われているんですね

[grape_ll]

reachのセミコロンを忘れていました．申し訳ございません．
しかし，私の手元ではtoo largeとなってコンパイルは通りませんでした．

N*Nの配列を作ろうと思ったわけは，それぞれの展望台から一回でいけるところを入力とほぼ同時に先に記録しておいて後から見てみれば，計算量を減らせるのではと考えたからです．

[退会済みユーザー]

確認したいんですけど、#define A 100　にしたらコンパイル通りますか？

あと、解説文の
「展望台 i から一本の道を使って辿り着けるどんな展望台よりも展望台 iの方が標高が高い」ことは、
「展望台 i から一本の道を使って辿り着ける展望台の標高の最大値よりも展望台 i の標高が高い」ことと等しいです。
という文の意味は分かりますか？

[grape_ll]

define A 100としたときにはコンパイルできました．
また，日本語の意味も読み取れているつもりです．

Answer 1

int型は大きい値を扱うときには不向きなので他の変数型で試してみましょう。long long型などは試してみましたか？

Comments

[grape_ll]

中に入れる値が大きいのではなく，入れる個数が大きいのですが，この時にもlonglongは有効なのでしょうか？自分の知識としては入れられる整数の範囲が大きくなっただけかと思っていたのですが．

ご指摘いただいた通り,longlong型でやってみましたら，vscode上ではコンパイル時にエラーが出なかったのですが，提出した後の結果ではすべてのケースでコンパイルエラーとなっていました．