Almost Same Codes, One AC ,Other WA for PERCAPTA

help
21

Nice Observation Buddy!
Still Getting WA After printing “\n”
WA Solution-Click Here

22

I am Sure (perhaps) that DFS Part is Correct but Not able to figure out Why i am getting WA. Even The AC code is similar.

One Difference more i want to add,
In AC Code i used visit array int visit[200005]={0};
In WA code i used unordered_map for visit unordered_map<int,int>visit;

But i don’t think that map will lead to WA.

23

You are storing a[i]/b[i] in int. So, this will always give WA. eg 4/5 and 3/5 both are 0. But according to ques only 4/5 should be considered

24

Test Cases are Week Buddy,
Through using int i got AC

25

Can you share that code?

26

Friend,
Just scroll up and reach where the discussion started i have mentioned all links.
:slightly_smiling_face:

27

Your mistake

int d=s.top();
          if(visit[d]==0)
          ans.pb(d+1);
          s.pop();
          visit[d]=1;
2 Likes
28

But its Obvious that it’s not visited through this loop:

for(int j=0;j<adj[d].size();j++)
      {
        if(visit[adj[d][j]]==0 && maxper==per[adj[d][j]])s.push(adj[d][j]);
      }

Becuase this loop controls whether while loop will end or not.
Am i right?

29

Yeah you’re right. If it’s in the stack, it’s not visited.
Although I’m not able to figure out why your WA is not passing.

1 Like
30

See, your code marks visited when value is popped. So, it is possible that, some value was already in stack but it can again be pushed because it is not visited.

1 Like
31

@sebastian You are a Genius,
My WA Code Passed , i just added the if condition
My WA Changed AC code- Click Here

2 Likes
32

Thnx man. I have faced the same mistake

33

Damn that’s right! Nice one.

34

But i am not able to digest this Reason Can You elaborate it?
As i just marked visited before pop operation and that again got WA.
@sebastian

35

Consider a square with diagonals connected (points from 1 to 4). We start with first vertex (say 1). Now the other three vertices will be pushed in stack. Till now vis[1]=1 and three value in stack. Now we mark vis[2]=1 and pop it. Now 2 is also connected to 3 vertices (1,3,4) .But only 3 and 4 will be pushed again as they have not been marked visited till now

2 Likes
36

Right! So we push the same nodes multiple times into the stack. Whenever I write my dfs, I mark the node visited right after pushing it as a convention. Nice to see how not doing that can cause problems!

37

Your Example is great but i am not able to relate it perfectly.Sorry for that.Can you give a simple example or explain the current example in more depth?Sorry for the dumbness :sweat_smile:

38

Run your dfs on a triangle (say vertices are 1,2,3). We first push 1 in stack. Now 1 is pop and vis[1]=1. Now 2 and 3 are pushed in stack. Now, 2 is pop and vis [2]=1. Now adj vertices of 2 are 1 and 3. But vis[1]=1. So, 3 will be pushed in stack. Now there are two 3 in stack. Hope you understood.

1 Like
39

Thank You So much @sebastian . I got the whole point. You are a genius!!
I was missing this point.Once again thanks :grin:

40

@aneee004 I was seeing your Your AC Solution.I Submitted this same solution which first gave TLE and when i changed it to scanf printf it gave WA.

Why AC code is giving WA?
Have they changed the test cases?
Your WA Solution - Click Here