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

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	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