Almost Same Codes, One AC ,Other WA for PERCAPTA

help
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

41

Not sure what happened when you submitted.
I tried submitting the same code, with fast I/O here and it passes.

[EDIT]: Well well well, you have used "%d" to scan a long long datatype. Here is the accepted solution with scanf() using the proper type specifier, that is "%lld".

1 Like
42

oh

43

Sorry Bro I made a mistake of not putting ll.
My bad :confused:

1 Like
44

Lol. I shouldn’t have used long long for A and B. Int is sufficient. In that case I should typecaste all the comparisons to LL though.

It’s good practice to keep all the variables as int, if long long isn’t necessary. The operations on int are also faster.

1 Like
45

Yes,You are Right.I Sometimes got TLE due to unnecessary use of long long int where int was sufficient.Sometimes endl also landed me with TLE.

1 Like