Why this code on "LIS on Tree" give TLE in one and on other gives accepted?

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

I implemented my solution using LIS(nlogn way) in this Problem F: LIS on Tree. Issue is I'm Facing that,by changing the position changing the snippet code where LIS is getting calculated is giving me correct answer but giving TLE(time limit exceeded) in other way. As far as i can see this does not change the time complexity any how. Am I missing something conceptually on knowledge of LIS or on DFS?

TLE When LIS calculation inside for loop

Code LINK:

**CODE SNIPPET:**
void dfs(int i,int parent,set<int>& seq,vector<int> &ar,vector<int> &ans)
{
    set<int> temp=seq;
    for(auto j:edges[i])
    {
        if(j!=parent)
        {
            seq=temp;
            if(seq.lower_bound(ar[j])!=seq.end())
            {
                //auto p1=*seq.lower_bound(ar[j]);
                seq.erase(seq.lower_bound(ar[j]));
                seq.insert(ar[j]);
                ans[j]=max(ans[j],(int)seq.size());
                dfs(j,i,seq,ar,ans);
                // seq.erase(ar[j]);
                // seq.insert(p1);
            }
            else
            {
                seq.insert(ar[j]);
                ans[j]=max(ans[j],(int)seq.size());
                dfs(j,i,seq,ar,ans);
                //seq.erase(ar[j]);
            }
            // for(auto p:seq)
            //     cout<<p<<" ";
            // cout<<"\n";
            
        }
    }
}

Accepted after changing LIS snippet outside for loop

Code LINK:

**CODE SNIPPET:**
void dfs(int i, int parent, set<int>& seq, vector<int> &ar, vector<int> &ans)
{
    int temp=-1;
    if (seq.lower_bound(ar[i]) != seq.end())
    {
        temp=*seq.lower_bound(ar[i]);
        seq.erase(seq.lower_bound(ar[i]));
        seq.insert(ar[i]);
    }
    else
        seq.insert(ar[i]);
    ans[i] = max(ans[i], (int)seq.size());
    for (auto j : edges[i])
    {
        if (j != parent)
        {
            dfs(j, i, seq, ar, ans);
        }
    }
    seq.erase(ar[i]);
    if(temp!=-1)
        seq.insert(temp);
}

Comments (1)

Show archived | Write comment?

will.earn.you

5 years ago, # |

← Rev. 3 →

In your first code the problem is in this line — set<int> temp=seq; because it copy original set to the new set with time complexity O(n). This is the reason why you first code is giving verdict TLE.

→ Reply

Sumanto's blog