Help in PRECAPTA

https://www.codechef.com/problems/PERCAPTA

#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define lld long long int 

lld a[200005],b[200005],n,m,x,y,vis[200005],chose[200005];
vector <lld> temp,v[200005];

void bfs(lld u)
{
    queue <lld> q;
    q.push(u);
    vis[u]=1;
    temp.push_back(u);
    while(!q.empty())
    {
        int val=q.front();
        q.pop();
        for(int i=0;i<v[val].size();i++)
        {
            if(!vis[v[val][i]] && chose[v[val][i]])
            {
                q.push(v[val][i]);
                vis[v[val][i]]=1;
                temp.push_back(v[val][i]);
            }
        }
    }
}

int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        
        for(int i=1;i<=n;i++)
        cin>>b[i];
        
        memset(chose,0,sizeof(chose));
        memset(vis,0,sizeof(vis));
        
        lld n=a[1],d=b[1];
        for(int i=2;i<=n;i++)
        {
            if(a[i]*d>b[i]*n)
            {
                n=a[i];
                d=b[i];
            }
        }
        
        for(int i=1;i<=n;i++)
        {
            if(a[i]*d==b[i]*n)
            chose[i]=1;
        }
        
        while(m--)
        {
            cin>>x>>y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        
        vector <lld> ans;
        for(int i=1;i<=n;i++)
        {
            if(chose[i]&&!vis[i])
            {
                temp.clear();
                bfs(i);
                if(temp.size()>ans.size())
                ans=temp;
            }
            
        }
        cout<<ans.size()<<"\n";
        for(int i=0;i<ans.size();i++)
        cout<<ans[i]<<" ";
        cout<<"\n";
        
        for(int i=0;i<=n;i++)
        v[i].clear();
        
    }
}

This is giving SIGSEV. Please tell me my mistake

Bro, I got my mistake. I have used same variable twice. Thanks @akshitm16

1 Like

Already answered
Link

1 Like

@akshitm16 hey buddy look into my code too please …
https://www.codechef.com/viewsolution/34636229

Link
The problem is with the commented part. I could’t really understand what were you doing there but I felt it was wrong so replaced it with regular bfs. You can check it.
I’ll revert back once I understand the commented part.

1 Like

thanks that was dfs in the commented part,

i used a vector temp_nodes to store every value that dfs read…

i am basically reading one connected sub graph of max_nodes in one go… i hope you can tell now what is wrong with that dfs commented part.

I felt that bfs instead of dfs.

1 Like

yes i tried it to be dfs though but because i didn’t used standard functions, so it behaved like a bfs :sweat_smile:. but either way this should have worked because we are trying find the max connected region.

Ya…it should have worked. I’m trying to find the mistake.

1 Like

i really don’t want to stress you out but, here is my submission for checkpoints problem. I have no idea at the moment why this submission is wrong. and i have tried to with all minor changes nothing gave me AC.

@admin Please consider showing us the test cases results for submission in practice session.

that would help us a lot in finding our mistake and would save us a huge time.

I’ve found the problem
Link
Like you were visiting same nodes again and again.
You may use this link as well

1 Like

basically i should have marked childred in inner most loop and not in the beginning. that was a really deep one, thanks a lot @akshitm16.

1 Like

Yes… You can generate simple test cases to analyze why was this happening-

test case
1
3 3
1 1 1
1 1 1
1 2
2 3
1 3
1 Like

here is something that still contradicts me, if we mark child node as visited in innermost loop, this would lead to no further movement from that child.

No, inside the while loop there is no such condition that will restrict it’s movement.

1 Like

yes the first condition if max is false then continue to check from next node. this was a problem arose due to the way i programmed it.

https://www.codechef.com/viewsolution/34637878

if i just put the output vecctor into a set it still works. this means

there were no cases in test case where max nodes were going to be in a difference depths and connected.

I don’t really understand what you mean by this-

there were no cases in test case where max nodes were going to be in a difference depths and connected.

if i just put the output vecctor into a set it still works

This thing is so obvious because you’re repeating nodes as I told earlier and using set will avoid it but it isn’t a good way as in the bfs part you were visiting same nodes again and thus wasting time and memory.

1 Like

sorry i misunderstood, thanks for your help.

I misunderstood that there double checks on visited nodes … but then i realised you delted the previous check and now i know where i was wrong, thankyou for bearing with me :sweat_smile:

can you help me here in this checkpoints problem now ? https://www.codechef.com/viewsolution/34625734

1 Like

Link
Overflow issues

1 Like

explain me about these please, i’m not that deep into programming.
and int can store upto 2B right? why is this happeniging after that our constrains are only 10**9