Code below in Darwin environment
c++-std=c++17-g3-fsanitize=address main.cc&./a.out results in heap-buffer-overflow.
After trying various things, it seems that the symptom is probably occurring in G[A].push_back(B);.
I would appreciate it if someone could tell me the cause of the bug.
Also, keep the problem and test code down.
https://atcoder.jp/contests/abc278/tasks/abc278_c
example input:
39
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
Current State Code:
#include<bits/stdc++.h>
using namespace std;
void solve() {
int N,Q;
cin>>N>Q;
vector<vector>int>>G(N);
for(inti=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(intB_friend:G[B]){
if(B_friend==A){
BaveA = true;
}
}
if(AhaveB&&BhaveA){
cout<<"Yes"<<endl;
} else{
cout<<"No"<<endl;
}
}
}
}
int main() {
// setup();
solve();
}
I think the cause is exactly what actorbug said.
std::vector, but in operator[],
This function is not specified to perform boundary checks unlike at() member functions.Depending on the standard library implementation, assert(n<size()) may check the boundaries
You can use at() to perform a range check at runtime, as described in .
The reason is G[A] access outside the subscript range.
vector<vector>int>G(N);
G is defined as above, so the subscripts range is from 0 to N-1.
In contrast, A ranges from 1 to N, depending on the problem.
Therefore, if G[A] is written, A is N, it is out of range access.
With g++, you can add -D_GLIBCXX_DEBUG to the command-line arguments at compile time to detect out-of-range access and issue error messages.However, in Darwin environment, the method may be different.
© 2024 OneMinuteCode. All rights reserved.