Abstract
Never use reference value on std::priority_queue
, otherwise it will be affected when you push in something "greater" than it. I lose my first chance to AK an ABC in this reason.
Detail
When I was solving D, I wrote this
while(q.size()){
auto& [stp,t1,t2]=q.top();
q.pop();
auto& [drx1,dry1]=t1;
auto& [drx2,dry2]=t2;
if(t1==t2){
printf("%d\n",stp);
exit(0);
}
for(int i=0;i<n;i++){
int nx1=drx1+dx[i],nx2=drx2+dx[i],
ny1=dry1+dy[i],ny2=dry2+dy[i];
if(max(nx1,ny1)>=n or min(nx1,ny1)<0 or s[nx1][ny1]=='#')nx1-=dx[i],ny1-=dy[i];
if(max(nx2,ny2)>=n or min(nx2,ny2)<0 or s[nx2][ny2]=='#')nx2-=dx[i],ny2-=dy[i];
if(vis[nx1][ny1][nx2][ny2])continue;
vis[nx1][ny1][nx2][ny2]=true;
q.push({stp+1,{nx1,ny1},{nx2,ny2}});
}
}
It seems no flaw in it, but when I input
5
....#
#..#.
.P...
..P..
....#
it threw segmentation fault.
Then, I add some debug code
...
printf("%d %d %d %d\n",drx1,dry1,drx2,dry2);
fflush(stdout);
...
printf("%d\n",i);
fflush(stdout);
...
printf("%d %d %d %d\n",nx1,ny1,nx2,ny2);
fflush(stdout);
in it, and it put
2 1 3 2
0
2 2 3 3
1
3 2 4 3
2
-14220976 545 -15256416 545
before it ran into the segmentation fault.
I realized that the container did something like cumulative sum. It's not what I want.
Then, I deleted all the character &
in my code and modified it to
while(q.size()){
auto [stp,t1,t2]=q.top();
q.pop();
auto [drx1,dry1]=t1;
auto [drx2,dry2]=t2;
if(t1==t2){
printf("%d\n",stp);
exit(0);
}
for(int i=0;i<4;i++){
int nx1=drx1+dx[i],nx2=drx2+dx[i],
ny1=dry1+dy[i],ny2=dry2+dy[i];
fflush(stdout);
if(max(nx1,ny1)>=n or min(nx1,ny1)<0 or s[nx1][ny1]=='#')nx1-=dx[i],ny1-=dy[i];
if(max(nx2,ny2)>=n or min(nx2,ny2)<0 or s[nx2][ny2]=='#')nx2-=dx[i],ny2-=dy[i];
printf("%d %d %d %d %d\n",stp,nx1,ny1,nx2,ny2);
if(vis[nx1][ny1][nx2][ny2])continue;
vis[nx1][ny1][nx2][ny2]=true;
q.push({stp+1,{nx1,ny1},{nx2,ny2}});
}
}
and it put
0 2 2 3 3
0 3 1 4 2
0 2 0 3 1
0 1 1 2 2
1 3 2 4 3
1 4 1 4 2
1 3 0 4 1
1 2 1 3 2
2 4 2 4 3
2 4 1 4 2
2 4 0 4 1
2 3 1 3 2
3 4 3 4 3
3 4 2 4 3
3 4 1 4 2
3 3 2 3 3
4
it's the wrong answer.
I spend about 5 minutes to realize that priority_queue
put the greatest element at the top, then I modified it a bit to
while(q.size()){
auto [stp,t1,t2]=q.top();
q.pop();
auto [drx1,dry1]=t1;
auto [drx2,dry2]=t2;
if(t1==t2){
printf("%d\n",-stp);
exit(0);
}
for(int i=0;i<4;i++){
int nx1=drx1+dx[i],nx2=drx2+dx[i],
ny1=dry1+dy[i],ny2=dry2+dy[i];
// fflush(stdout);
if(max(nx1,ny1)>=n or min(nx1,ny1)<0 or s[nx1][ny1]=='#')nx1-=dx[i],ny1-=dy[i];
if(max(nx2,ny2)>=n or min(nx2,ny2)<0 or s[nx2][ny2]=='#')nx2-=dx[i],ny2-=dy[i];
// printf("%d %d %d %d %d\n",stp+1,nx1,ny1,nx2,ny2);
if(vis[nx1][ny1][nx2][ny2])continue;
vis[nx1][ny1][nx2][ny2]=true;
q.push({stp-1,{nx1,ny1},{nx2,ny2}});
}
}
then it finally put the correct answer.
Thanks atcoder_official for your lesson, and the easiest G ever that's also the first G I solved during the contest.
it actually occurs to not only priority_queue but also other STL data structures like queue, deque, vector, map, ...
UPD: What I mentioned below is actually wrong. Iterators, reference and pointers of STL container elements will not always work after structure modification due to special allocation logic to maintain mutable vector sizes. However, modifying the value of elements without pushing or popping in some linear dses like
queue
andvector
is usable.For linear data structures like
queue
,deque
,vector
reference is guaranteed to work.The reason why it doesn't work for
priority_queue
andmap
is that they use data structures called balance trees and heaps, which does not support modification to arbitrary elements without modifying the structure.I actually don't think so, there was one time when I used a
queue <vector <int>>
and then used the reference of the front one after it'd been deleted. It was horrible and took me about an hour to realise it.then what do you expect from wild references
meh, it was a long time ago when I was a newbie so I call it a lesson
That is not true: if you have something like
std::vector<int> vec (1, 2); int &a = vec[0]
, then the referencea
will point to garbage values once you push things to the back ofvec
(because at some point, the vector will exceed its capacity and will be reallocated).Oh my god -is-this-fft-
Thanks for your explanation