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

#	User	Rating
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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

4 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