0

下記のコードをDarwin環境で
c++ -std=c++17 -g3 -fsanitize=address main.cc && ./a.out として実行すると、heap-buffer-overflow となってしまいます。
色々試してみたところ、おそらく G[A].push_back(B); でその現象が起きているっぽいです。
どなたかバグの原因を教えていただけると助かります。
また問題とテストコードも下に置いておきます。

https://atcoder.jp/contests/abc278/tasks/abc278_c

入力例:

3 9
1 1 2
3 1 2
1 2 1
3 1 2
1 2 3
1 3 2
3 1 3
2 1 2
3 1 2

現状のコード:

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int N, Q;
    cin >> N >> Q;
    vector<vector<int>> G(N);
    for (int i = 0; i < Q; i++) {
        int 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 (int A_friend: G[A]) {
                if (A_friend == B) {
                    AhaveB = true;
                }
            }
            bool BhaveA = false;
            for (int B_friend: G[B]) {
                if (B_friend == A) {
                    BhaveA = true;
                }
            }
            if (AhaveB && BhaveA) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
    }
}

int main() {
//  setup();
    solve();
}
0

2 件の回答 2

0

原因は actorbug さんの回答通りだと思います。

std::vectorですが、 operator[]

この関数は、at()メンバ関数とちがって境界チェックを行うことが規定されない。標準ライブラリの実装によってはassert(n < size())による境界チェックが行われる場合がある

と説明されているように、 at() を使えば実行時に範囲チェックを行うことができます。

1
  • 大変勉強になります。 コード内のvector<vector<int>> G(N)の添字部分をG(N + 1)にしたところ 基礎的なケースに関しては動いたのですが、一部REとなってしまい、その原因がわからないので、もしよろしければ教えていただけると大変助かります。 Commented 2022年11月20日 11:30
0

原因は、G[A]における、添え字の範囲外アクセスです。

vector<vector<int>> G(N);

Gは上のように定義しているので、添え字の範囲は、0~N-1です。
それに対し、Aの範囲は、問題によると1~Nです。
よって、G[A]と書いた場合、AがNだと範囲外アクセスになります。

g++なら、コンパイル時のコマンドライン引数に-D_GLIBCXX_DEBUGを追加することで、範囲外アクセスを検出してエラーメッセージを出してくれるようになります。ただ、Darwin環境だとやり方が違うかもしれません。

1
  • 問題点のみならずデバッグ方法まで教えていただきありがとうございます。 また本問を<vector<vector<int>>>G(N + 1)のように定義し直してみたところ、basicなケースではACとなったのですが、いくつかのケースでRC(コンパイルエラー)となってしまいその原因がわからないでいます。 教えていただけると大変助かります Commented 2022年11月20日 11:33

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

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