0

隣接リストを実装しようとした時に heap-buffer-overflow が発生してしまう
こちらのリンクで質問させいていただいた問題の続きなのですが、なぜ本問題においてあるケースにおいてRE(実行時エラー)となってしまうのか、原因が特定できていません。
わかる方いらっしゃいましたら教えていただけると助かります。
[追記]
あるケースと上の文で言っているケースに関してはAtCoderでテストケースが公開されていないため自分でもわかっていません。
ご指摘くださった方ありがとうございます。

#include <bits/stdc++.h>

using namespace std;

void solve() {
    uint64_t N, Q;
    cin >> N >> Q;
    vector<vector<uint64_t>> G(N + 1);
    for (uint64_t i = 0; i < Q; i++) {
        uint64_t T, A, B;
        cin >> T >> A >> B;
        if (T == 1) {
            auto itr = find(G[A].begin(), G[A].end(), B);
            if (itr == G[A].end()) {
                G[A].push_back(B);
            }
        }
        if (T == 2) {
            auto itr = find(G[A].begin(), G[A].end(), B);
            if (itr != G[A].end()) {
                G[A].erase(itr);
            }
        }
        if (T == 3) {
            bool AhaveB = false;
            for (uint64_t A_friend: G[A]) {
                if (A_friend == B) {
                    AhaveB = true;
                }
            }
            bool BhaveA = false;
            for (uint64_t B_friend: G[B]) {
                if (B_friend == A) {
                    BhaveA = true;
                }
            }
            if (AhaveB && BhaveA) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
    }
}

int main() {
    solve();
}

上記のように変更を加えました。
以下問題です。
https://atcoder.jp/contests/abc278/tasks/abc278_c

2
  • 1
    「あるケースにおいてRE(実行時エラー)」の詳細な状況を追記した方が良いと思われます。
    – kunif
    Commented 2022年11月20日 13:34
  • 私もそのケースが特定できればしておきたいのですが、AtCoder社が公開していないためこのような書き方をさせていただきました。。 Commented 2022年11月20日 20:45

1 件の回答 1

0

出題には

制約

2≤N≤109

とありました。

vector<vector<uint64_t>> G(N + 1);

uint64_tは8バイトなのでGは109 x 8 = 8GB 消費することになります。これはメモリ上限を超えているのではないでしょうか?

4
  • ご返信ありがとうございます。 uint64_tint64_tint32_tに変更しても同様のエラーとなってしまいます。。 Commented 2022年11月20日 20:41
  • 1
    横から失礼します。int64_tは8バイト(Gのサイズ8GB)、int32_tは4バイト(同4GB)なので、型を変えるだけでは無理です。そもそもvectorを使うこと自体に無理があります。
    – actorbug
    Commented 2022年11月20日 20:56
  • 1
    そもそも、Gはvector<uint64_t>のvectorなので、要素のサイズは24バイト(g++ 11.3.0で確認)のはずです。uint64_tの部分を書き換えても、サイズは変わりません。
    – actorbug
    Commented 2022年11月20日 21:03
  • なるほど、vectorであればそもそも持つ型によらず24byteだったんですね。 確かにこれを大きなサイズ持つと実行時エラーになりますね。。 とても勉強になりました。ありがとうございます Commented 2022年11月20日 21:43

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。