TLE in TREDIFF

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

#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 

//-4%3=-1
vector <int> edge[1000001],res;
int vis[1000001]={-1};
int n,arr[1000001];

void dfs(int x,int y,vector <int> v)
{
    v.push_back(x);
    
    if(x==y)
    {
        for(int i=0;i<v.size();i++)
        {
            res.push_back(arr[v[i]]);
        }
        return;
    }
    
    vis[x]=1;
    int flag = 0; 
    if(!edge[x].empty())
    { 
        for(int j=0;j<edge[x].size();j++)
        { 
            if (vis[edge[x][j]]==-1)
            { 
                dfs(edge[x][j],y,v); 
                flag = 1; 
            } 
        } 
    } 
    if (flag == 0)
    { 
        v.pop_back();
    } 
} 

int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t;
    cin>>t;
    while(t--)
    {
        int q,a,b;
        cin>>n>>q;

        for(int i=1;i<=n;i++)
        cin>>arr[i];
        
        for(int i=0;i<n-1;i++)
        {
            cin>>a>>b;
            edge[a].push_back(b);
            edge[b].push_back(a);
        }
        while(q--)
        {
            cin>>a>>b;
            //memset(vis,-1,sizeof(vis));
            
            for(int i=0;i<=1001;i++)
            vis[i]=-1;
            vector <int> v;
            res.clear();
            dfs(a,b,v);
            
            /*cout<<"\n";
            for(int i=0;i<res.size();i++)
            cout<<res[i]<<" ";*/
            
            sort(res.begin(),res.end());
            int r=INT_MAX;
            for(int i=0;i<res.size()-1;i++)
            r=min(r,abs(res[i]-res[i+1]));
            cout<<r<<"\n";
        }
    }
}

Why is this giving TLE for subtask 1? I have used dfs per query.
@galencolin @ssjgz @everule1

Amongst other things (e.g. passing v by value in dfs), you’re also making exactly the same mistake as this guy (and countless others in that thread).

Stamping out this CP anti-pattern is probably top of my if I ruled the world list :slight_smile:

2 Likes

I didn’t get the point :pensive: Would you explain me little more?

Try this test input; it won’t TLE, but it should give you a hint about what is going on (and what is causing your TLE):

5
6 3
10 2 5 6 5 6
1 2
2 3
2 4
1 5
5 6
5 6
3 5
1 4
6 3
10 2 5 6 5 6
1 2
2 3
2 4
1 5
5 6
5 6
3 5
1 4
6 3
10 2 5 6 5 6
1 2
2 3
2 4
1 5
5 6
5 6
3 5
1 4
6 3
10 2 5 6 5 6
1 2
2 3
2 4
1 5
5 6
5 6
3 5
1 4
6 3
10 2 5 6 5 6
1 2
2 3
2 4
1 5
5 6
5 6
3 5
1 4
6 3
2 Likes

Oh my mistake was not clearing edge vector ? Did I have made any other mistake?
N,Q<=1000 is for each TC or overall?

Yes. Or more fundamentally: this.

Passing v by value is another one.

The wording suggests “each TC”.

1 Like

How passing v by value is giving TLE?

https://www.codechef.com/viewsolution/33564974
After changes, but this is also giving tLE

You’re still passing v by value.

1 Like

Yeah, why passing by value giving TLE?
Now it turned into WA https://www.codechef.com/viewsolution/33566699

Passing by value copies the vector every time you pass it; passing by reference does not.

2 Likes

Oh but having globally vector v is giving WA :pensive:

I meant “pass v by reference”, not “make v global” XD

1 Like

In both case it is giving WA. https://www.codechef.com/viewsolution/33567304

Why are you only sometimes calling v.pop_back()?

2 Likes

Finally got it. Thanks a lot!!

1 Like

I dislike your hate for global variables, they make function headers much less ugly

3 Likes

I saw the editorial and designed my code in that way but i am getting runtime error when i submit my code.
It would be great help if you could tell e why its giving SIGSEV.
https://www.codechef.com/viewsolution/33577600
Thanks again.

It’s quite a bad idea to return in the middle of a test case, especially before reading in all the input

Ya, my bad i shared the wrong solution. This is giving SIGSEV despite the fact of not returning and doing everything else the same way.
https://www.codechef.com/viewsolution/33585543
It would be nice if you could point out what us going wrong for a beginner like me.
Thanks.